Skip to main content

Longest Bitonic Subsequence

Here given code implementation process.

// C program for
// Longest Bitonic Subsequence
#include <stdio.h>
#include <stdlib.h>

// Display the  given array elements
void printData(int arr[], int n)
{
    // Execute loop through by array length n
    for (int i = 0; i < n; ++i)
    {
        printf("  %d", arr[i]);
    }
    printf("\n");
}
// This is find the length of longest bitonic subsequence
void findLBS(int arr[], int n)
{
    if (n <= 0)
    {
        return;
    }
    // Loop controlling variable (i and j)
    int i = 0;
    int j = 0;
    // resulant sequence
    int max = 1;
    // Define two auxiliary array of n integer elements
    // List of incressing subsequence
    int increasing[n];
    //list of decreasing subsequence
    int decreasing[n];
    // Initial assign one to each of auxiliary array
    // Because each element can be first element of bitonic sequence
    for (i = 0; i < n; i++)
    {
        increasing[i] = 1;
        decreasing[i] = 1;
    }
    // Find increasing bitonic subsequence
    // Outer loop execute through from 1..n
    for (i = 1; i < n; ++i)
    {
        // Range of inner loop from 0 to n
        for (j = 0; j < i; ++j)
        {
            if (i != j 
                && arr[i] > arr[j] 
                && increasing[i] < increasing[j] + 1)
            {
                increasing[i] = increasing[j] + 1;
            }
        }
    }
    // Find longest decreasing subsequence
    // Right to left direction
    for (i = n - 2; i >= 0; --i)
    {
        for (j = n - 1; j > i; --j)
        {
            if (arr[i] > arr[j] 
                && 
                decreasing[i] < decreasing[j] + 1)
            {
                decreasing[i] = decreasing[j] + 1;
            }
        }
    }
    // Calculate resultant LSB
    for (i = 0; i < n; ++i)
    {
        if (increasing[i] + decreasing[i] - 1 > max)
        {
            max = increasing[i] + decreasing[i] - 1;
        }
    }
    // Display array elements
    printf("\n Array \n");
    printData(arr, n);
    // Display calculated result
    printf(" Length of LBS %d\n", max);
}
int main()
{
    // Given integer element
    int arr[] = {
        6, 7, 1, 5, 3, 2, 4, 9, 3, 2, 8, 7
    };
    // Get the number of element
    int n = sizeof(arr) / sizeof(arr[0]);
    
    // Test 
    // (6, 7, 5, 4, 3, 2)
    findLBS(arr, n);
    return 0;
}

Output

 Array
  6  7  1  5  3  2  4  9  3  2  8  7
 Length of LBS 6
/*
  Java Program 
  Longest Bitonic Subsequence
*/
class BitonicSubsequence
{
	// Display the  given array elements
	public void printData(int[] arr, int n)
	{
		// Execute loop through by array length n
		for (int i = 0; i < n; ++i)
		{
			System.out.print("  " + arr[i]);
		}
		System.out.print("\n");
	}
	// This is find the length of longest bitonic subsequence
	public void findLBS(int[] arr, int n)
	{
		if (n <= 0)
		{
			return;
		}
		// Loop controlling variable (i and j)
		int i = 0;
		int j = 0;
		// resulant sequence
		int max = 1;
		// Define two auxiliary array of n integer elements
		// List of incressing subsequence
		int[] increasing = new int[n];
		//list of decreasing subsequence
		int[] decreasing = new int[n];
		// Initial assign one to each of auxiliary array
		// Because each element can be first element of bitonic sequence
		for (i = 0; i < n; i++)
		{
			increasing[i] = 1;
			decreasing[i] = 1;
		}
		// Find increasing bitonic subsequence
		// Outer loop execute through from 1..n
		for (i = 1; i < n; ++i)
		{
			// Range of inner loop from 0 to n
			for (j = 0; j < i; ++j)
			{
				if (i != j && arr[i] > arr[j] 
                    && increasing[i] < increasing[j] + 1)
				{
					increasing[i] = increasing[j] + 1;
				}
			}
		}
		// Find longest decreasing subsequence
		// Right to left direction
		for (i = n - 2; i >= 0; --i)
		{
			for (j = n - 1; j > i; --j)
			{
				if (arr[i] > arr[j] 
                    && decreasing[i] < decreasing[j] + 1)
				{
					decreasing[i] = decreasing[j] + 1;
				}
			}
		}
		// Calculate resultant LSB
		for (i = 0; i < n; ++i)
		{
			if (increasing[i] + decreasing[i] - 1 > max)
			{
				max = increasing[i] + decreasing[i] - 1;
			}
		}
		// Display array elements
		System.out.print("\n Array \n");
		printData(arr, n);
		// Display calculated result
		System.out.print(" Length of LBS " + max + "\n");
	}
	public static void main(String[] args)
	{
		BitonicSubsequence task = new BitonicSubsequence();
		// Given integer element
		int[] arr = {
			6 , 7 , 1 , 5 , 3 , 2 , 4 , 9 , 3 , 2 , 8 , 7
		};
		// Get the number of element
		int n = arr.length;
		// Test 
		// (6, 7, 5, 4, 3, 2)
		task.findLBS(arr, n);
	}
}

Output

 Array
  6  7  1  5  3  2  4  9  3  2  8  7
 Length of LBS 6
// Include header file
#include <iostream>

using namespace std;
/*
  C++ Program 
  Longest Bitonic Subsequence
*/
class BitonicSubsequence
{
	public:
    // Display the  given array elements
    void printData(int arr[], int n)
    {
        // Execute loop through by array length n
        for (int i = 0; i < n; ++i)
        {
          cout << "  " << arr[i];
        }
        cout << "\n";
    }
	// This is find the length of longest bitonic subsequence
	void findLBS(int arr[], int n)
	{
		if (n <= 0)
		{
			return;
		}
		// Loop controlling variable (i and j)
		int i = 0;
		int j = 0;
		// resulant sequence
		int max = 1;
		// Define two auxiliary array of n integer elements
		// List of incressing subsequence
		int *increasing = new int[n];
		//list of decreasing subsequence
		int *decreasing = new int[n];
		// Initial assign one to each of auxiliary array
		// Because each element can be first element of bitonic sequence
		for (i = 0; i < n; i++)
		{
			increasing[i] = 1;
			decreasing[i] = 1;
		}
		// Find increasing bitonic subsequence
		// Outer loop execute through from 1..n
		for (i = 1; i < n; ++i)
		{
			// Range of inner loop from 0 to n
			for (j = 0; j < i; ++j)
			{
				if (i != j && arr[i] > arr[j] && increasing[i] < increasing[j] + 1)
				{
					increasing[i] = increasing[j] + 1;
				}
			}
		}
		// Find longest decreasing subsequence
		// Right to left direction
		for (i = n - 2; i >= 0; --i)
		{
			for (j = n - 1; j > i; --j)
			{
				if (arr[i] > arr[j] && decreasing[i] < decreasing[j] + 1)
				{
					decreasing[i] = decreasing[j] + 1;
				}
			}
		}
		// Calculate resultant LSB
		for (i = 0; i < n; ++i)
		{
			if (increasing[i] + decreasing[i] - 1 > max)
			{
				max = increasing[i] + decreasing[i] - 1;
			}
		}
		// Display array elements
		cout << "\n Array \n";
		this->printData(arr, n);
		// Display calculated result
		cout << " Length of LBS " << max << "\n";
	}
};
int main()
{
	BitonicSubsequence task = BitonicSubsequence();
	// Given integer element
	int arr[] = {
		6 , 7 , 1 , 5 , 3 , 2 , 4 , 9 , 3 , 2 , 8 , 7
	};
	// Get the number of element
	int n = sizeof(arr) / sizeof(arr[0]);
	// Test
	// (6, 7, 5, 4, 3, 2)
	task.findLBS(arr, n);
	return 0;
}

Output

 Array
  6  7  1  5  3  2  4  9  3  2  8  7
 Length of LBS 6
// Include namespace system
using System;
/*
  C# Program 
  Longest Bitonic Subsequence
*/
public class BitonicSubsequence
{
	// Display the  given array elements
	public void printData(int[] arr, int n)
	{
		// Execute loop through by array length n
		for (int i = 0; i < n; ++i)
		{
			Console.Write("  " + arr[i]);
		}
		Console.Write("\n");
	}
	// This is find the length of longest bitonic subsequence
	public void findLBS(int[] arr, int n)
	{
		if (n <= 0)
		{
			return;
		}
		// Loop controlling variable (i and j)
		int i = 0;
		int j = 0;
		// resulant sequence
		int max = 1;
		// Define two auxiliary array of n integer elements
		// List of incressing subsequence
		int[] increasing = new int[n];
		//list of decreasing subsequence
		int[] decreasing = new int[n];
		// Initial assign one to each of auxiliary array
		// Because each element can be first element of bitonic sequence
		for (i = 0; i < n; i++)
		{
			increasing[i] = 1;
			decreasing[i] = 1;
		}
		// Find increasing bitonic subsequence
		// Outer loop execute through from 1..n
		for (i = 1; i < n; ++i)
		{
			// Range of inner loop from 0 to n
			for (j = 0; j < i; ++j)
			{
				if (i != j && arr[i] > arr[j] && increasing[i] < increasing[j] + 1)
				{
					increasing[i] = increasing[j] + 1;
				}
			}
		}
		// Find longest decreasing subsequence
		// Right to left direction
		for (i = n - 2; i >= 0; --i)
		{
			for (j = n - 1; j > i; --j)
			{
				if (arr[i] > arr[j] && decreasing[i] < decreasing[j] + 1)
				{
					decreasing[i] = decreasing[j] + 1;
				}
			}
		}
		// Calculate resultant LSB
		for (i = 0; i < n; ++i)
		{
			if (increasing[i] + decreasing[i] - 1 > max)
			{
				max = increasing[i] + decreasing[i] - 1;
			}
		}
		// Display array elements
		Console.Write("\n Array \n");
		printData(arr, n);
		// Display calculated result
		Console.Write(" Length of LBS " + max + "\n");
	}
	public static void Main(String[] args)
	{
		BitonicSubsequence task = new BitonicSubsequence();
		// Given integer element
		int[] arr = {
			6 , 7 , 1 , 5 , 3 , 2 , 4 , 9 , 3 , 2 , 8 , 7
		};
		// Get the number of element
		int n = arr.Length;
		// Test
		// (6, 7, 5, 4, 3, 2)
		task.findLBS(arr, n);
	}
}

Output

 Array
  6  7  1  5  3  2  4  9  3  2  8  7
 Length of LBS 6
<?php
/*
  Php Program 
  Longest Bitonic Subsequence
*/
class BitonicSubsequence
{
	// Display the  given array elements
	public	function printData( & $arr, $n)
	{
		// Execute loop through by array length n
		for ($i = 0; $i < $n; ++$i)
		{
			echo "  ". $arr[$i];
		}
		echo "\n";
	}
	// This is find the length of longest bitonic subsequence
	public	function findLBS( & $arr, $n)
	{
		if ($n <= 0)
		{
			return;
		}
		// Loop controlling variable (i and j)
		$i = 0;
		$j = 0;
		// resulant sequence
		$max = 1;
		// Define two auxiliary array of n integer elements
		// Initial assign one to each of auxiliary array
		// Because each element can be first element of bitonic sequence
		// List of incressing subsequence
		$increasing = array_fill(0, $n, 1);
		//list of decreasing subsequence
		$decreasing = array_fill(0, $n, 1);
		// Find increasing bitonic subsequence
		// Outer loop execute through from 1..n
		for ($i = 1; $i < $n; ++$i)
		{
			// Range of inner loop from 0 to n
			for ($j = 0; $j < $i; ++$j)
			{
				if ($i != $j && $arr[$i] > $arr[$j] 
                    && $increasing[$i] < $increasing[$j] + 1)
				{
					$increasing[$i] = $increasing[$j] + 1;
				}
			}
		}
		// Find longest decreasing subsequence
		// Right to left direction
		for ($i = $n - 2; $i >= 0; --$i)
		{
			for ($j = $n - 1; $j > $i; --$j)
			{
				if ($arr[$i] > $arr[$j] 
                    && $decreasing[$i] < $decreasing[$j] + 1)
				{
					$decreasing[$i] = $decreasing[$j] + 1;
				}
			}
		}
		// Calculate resultant LSB
		for ($i = 0; $i < $n; ++$i)
		{
			if ($increasing[$i] + $decreasing[$i] - 1 > $max)
			{
				$max = $increasing[$i] + $decreasing[$i] - 1;
			}
		}
		// Display array elements
		echo "\n Array \n";
		$this->printData($arr, $n);
		// Display calculated result
		echo " Length of LBS ". $max ."\n";
	}
}

function main()
{
	$task = new BitonicSubsequence();
	// Given integer element
	$arr = array(6, 7, 1, 5, 3, 2, 4, 9, 3, 2, 8, 7);
	// Get the number of element
	$n = count($arr);
	$task->findLBS($arr, $n);
}
main();

Output

 Array
  6  7  1  5  3  2  4  9  3  2  8  7
 Length of LBS 6
/*
  Node Js Program 
  Longest Bitonic Subsequence
*/
class BitonicSubsequence
{
	// Display the  given array elements
	printData(arr, n)
	{
		// Execute loop through by array length n
		var i = 0;
		while (i < n)
		{
			process.stdout.write("  " + arr[i]);
			++i;
		}
		process.stdout.write("\n");
	}
	// This is find the length of longest bitonic subsequence
	findLBS(arr, n)
	{
		if (n <= 0)
		{
			return;
		}
		// Loop controlling variable (i and j)
		var i = 0;
		var j = 0;
		// resulant sequence
		var max = 1;
		// Define two auxiliary array of n integer elements
		// Initial assign one to each of auxiliary array
		// Because each element can be first element of bitonic sequence
		// List of incressing subsequence
		var increasing = Array(n).fill(1);
		//list of decreasing subsequence
		var decreasing = Array(n).fill(1);
		i = 1;
		// Find increasing bitonic subsequence
		// Outer loop execute through from 1..n
		while (i < n)
		{
			j = 0;
			// Range of inner loop from 0 to n
			while (j < i)
			{
				if (i != j && arr[i] > arr[j] 
                    && increasing[i] < increasing[j] + 1)
				{
					increasing[i] = increasing[j] + 1;
				}
				++j;
			}
			++i;
		}
		i = n - 2;
		// Find longest decreasing subsequence
		// Right to left direction
		while (i >= 0)
		{
			j = n - 1;
			while (j > i)
			{
				if (arr[i] > arr[j] 
                    && decreasing[i] < decreasing[j] + 1)
				{
					decreasing[i] = decreasing[j] + 1;
				}
				--j;
			}
			--i;
		}
		i = 0;
		// Calculate resultant LSB
		while (i < n)
		{
			if (increasing[i] + decreasing[i] - 1 > max)
			{
				max = increasing[i] + decreasing[i] - 1;
			}
			++i;
		}
		// Display array elements
		process.stdout.write("\n Array \n");
		this.printData(arr, n);
		// Display calculated result
		process.stdout.write(" Length of LBS " + max + "\n");
	}
}

function main()
{
	var task = new BitonicSubsequence();
	// Given integer element
	var arr = [6, 7, 1, 5, 3, 2, 4, 9, 3, 2, 8, 7];
	// Get the number of element
	var n = arr.length;
	// Test
	// (6, 7, 5, 4, 3, 2)
	task.findLBS(arr, n);
}
main();

Output

 Array
  6  7  1  5  3  2  4  9  3  2  8  7
 Length of LBS 6
#   Python 3 Program 
#   Longest Bitonic Subsequence

class BitonicSubsequence :
	#  Display the  given list elements
	def printData(self, arr, n) :
		#  Execute loop through by list length n
		i = 0
		while (i < n) :
			print("  ", arr[i], end = "")
			i += 1
		
		print(end = "\n")
	
	#  This is find the length of longest bitonic subsequence
	def findLBS(self, arr, n) :
		if (n <= 0) :
			return
		
		#  Loop controlling variable (i and j)
		i = 0
		j = 0
		#  resulant sequence
		max = 1
		#  Define two auxiliary list of n integer elements
		#  Initial assign one to each of auxiliary list
		#  Because each element can be first element of bitonic sequence
		#  List of incressing subsequence
		increasing = [1] * (n)
		# list of decreasing subsequence
		decreasing = [1] * (n)
		i = 1
		#  Find increasing bitonic subsequence
		#  Outer loop execute through from 1..n
		while (i < n) :
			j = 0
			#  Range of inner loop from 0 to n
			while (j < i) :
				if (i != j and arr[i] > arr[j] and 
                	increasing[i] < increasing[j] + 1) :
					increasing[i] = increasing[j] + 1
				
				j += 1
			
			i += 1
		
		i = n - 2
		#  Find longest decreasing subsequence
		#  Right to left direction
		while (i >= 0) :
			j = n - 1
			while (j > i) :
				if (arr[i] > arr[j] and 
                    decreasing[i] < decreasing[j] + 1) :
					decreasing[i] = decreasing[j] + 1
				
				j -= 1
			
			i -= 1
		
		i = 0
		#  Calculate resultant LSB
		while (i < n) :
			if (increasing[i] + decreasing[i] - 1 > max) :
				max = increasing[i] + decreasing[i] - 1
			
			i += 1
		
		#  Display list elements
		print("\n Array ")
		self.printData(arr, n)
		#  Display calculated result
		print(" Length of LBS ", max )
	

def main() :
	task = BitonicSubsequence()
	#  Given integer element
	arr = [6, 7, 1, 5, 3, 2, 4, 9, 3, 2, 8, 7]
	#  Get the number of element
	n = len(arr)
	#  Test
	#  (6, 7, 5, 4, 3, 2)
	task.findLBS(arr, n)

if __name__ == "__main__": main()

Output

 Array
   6   7   1   5   3   2   4   9   3   2   8   7
 Length of LBS  6
#   Ruby Program 
#   Longest Bitonic Subsequence

class BitonicSubsequence 
	#  Display the  given array elements
	def printData(arr, n) 
		#  Execute loop through by array length n
		i = 0
		while (i < n) 
			print("  ", arr[i])
			i += 1
		end

		print("\n")
	end

	#  This is find the length of longest bitonic subsequence
	def findLBS(arr, n) 
		if (n <= 0) 
			return
		end

		#  Loop controlling variable (i and j)
		i = 0
		j = 0
		#  resulant sequence
		max = 1
		#  Define two auxiliary array of n integer elements
		#  Initial assign one to each of auxiliary array
		#  Because each element can be first element of bitonic sequence
		#  List of incressing subsequence
		increasing = Array.new(n) {1}
		# list of decreasing subsequence
		decreasing = Array.new(n) {1}
		i = 1
		#  Find increasing bitonic subsequence
		#  Outer loop execute through from 1..n
		while (i < n) 
			j = 0
			#  Range of inner loop from 0 to n
			while (j < i) 
				if (i != j && arr[i] > arr[j] && 
                    increasing[i] < increasing[j] + 1) 
					increasing[i] = increasing[j] + 1
				end

				j += 1
			end

			i += 1
		end

		i = n - 2
		#  Find longest decreasing subsequence
		#  Right to left direction
		while (i >= 0) 
			j = n - 1
			while (j > i) 
				if (arr[i] > arr[j] && 
                    decreasing[i] < decreasing[j] + 1) 
					decreasing[i] = decreasing[j] + 1
				end

				j -= 1
			end

			i -= 1
		end

		i = 0
		#  Calculate resultant LSB
		while (i < n) 
			if (increasing[i] + decreasing[i] - 1 > max) 
				max = increasing[i] + decreasing[i] - 1
			end

			i += 1
		end

		#  Display array elements
		print("\n Array \n")
		self.printData(arr, n)
		#  Display calculated result
		print(" Length of LBS ", max ,"\n")
	end

end

def main() 
	task = BitonicSubsequence.new()
	#  Given integer element
	arr = [6, 7, 1, 5, 3, 2, 4, 9, 3, 2, 8, 7]
	#  Get the number of element
	n = arr.length
	#  Test
	#  (6, 7, 5, 4, 3, 2)
	task.findLBS(arr, n)
end

main()

Output

 Array 
  6  7  1  5  3  2  4  9  3  2  8  7
 Length of LBS 6

/*
  Scala Program 
  Longest Bitonic Subsequence
*/
class BitonicSubsequence
{
	// Display the  given array elements
	def printData(arr: Array[Int], n: Int): Unit = {
		// Execute loop through by array length n
		var i: Int = 0;
		while (i < n)
		{
			print("  " + arr(i));
			i += 1;
		}
		print("\n");
	}
	// This is find the length of longest bitonic subsequence
	def findLBS(arr: Array[Int], n: Int): Unit = {
		if (n <= 0)
		{
			return;
		}
		// Loop controlling variable (i and j)
		var i: Int = 0;
		var j: Int = 0;
		// resulant sequence
		var max: Int = 1;
		// Define two auxiliary array of n integer elements
		// Initial assign one to each of auxiliary array
		// Because each element can be first element of bitonic sequence
		// List of incressing subsequence
		var increasing: Array[Int] = Array.fill[Int](n)(1);
		//list of decreasing subsequence
		var decreasing: Array[Int] = Array.fill[Int](n)(1);
		i = 1;
		// Find increasing bitonic subsequence
		// Outer loop execute through from 1..n
		while (i < n)
		{
			j = 0;
			// Range of inner loop from 0 to n
			while (j < i)
			{
				if (i != j && arr(i) > arr(j) && increasing(i) < increasing(j) + 1)
				{
					increasing(i) = increasing(j) + 1;
				}
				j += 1;
			}
			i += 1;
		}
		i = n - 2;
		// Find longest decreasing subsequence
		// Right to left direction
		while (i >= 0)
		{
			j = n - 1;
			while (j > i)
			{
				if (arr(i) > arr(j) && decreasing(i) < decreasing(j) + 1)
				{
					decreasing(i) = decreasing(j) + 1;
				}
				j -= 1;
			}
			i -= 1;
		}
		i = 0;
		// Calculate resultant LSB
		while (i < n)
		{
			if (increasing(i) + decreasing(i) - 1 > max)
			{
				max = increasing(i) + decreasing(i) - 1;
			}
			i += 1;
		}
		// Display array elements
		print("\n Array \n");
		this.printData(arr, n);
		// Display calculated result
		print(" Length of LBS " + max + "\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: BitonicSubsequence = new BitonicSubsequence();
		// Given integer element
		var arr: Array[Int] = Array(6, 7, 1, 5, 3, 2, 4, 9, 3, 2, 8, 7);
		// Get the number of element
		var n: Int = arr.length;
		// Test
		// (6, 7, 5, 4, 3, 2)
		task.findLBS(arr, n);
	}
}

Output

 Array
  6  7  1  5  3  2  4  9  3  2  8  7
 Length of LBS 6
/*
  Swift 4 Program 
  Longest Bitonic Subsequence
*/
class BitonicSubsequence
{
	// Display the  given array elements
	func printData(_ arr: [Int], _ n: Int)
	{
		// Execute loop through by array length n
		var i: Int = 0;
		while (i < n)
		{
			print("  ", arr[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	// This is find the length of longest bitonic subsequence
	func findLBS(_ arr: [Int], _ n: Int)
	{
		if (n <= 0)
		{
			return;
		}
		// Loop controlling variable (i and j)
		var i: Int = 0;
		var j: Int = 0;
		// resulant sequence
		var max: Int = 1;
		// Define two auxiliary array of n integer elements
		// Initial assign one to each of auxiliary array
		// Because each element can be first element of bitonic sequence
		// List of incressing subsequence
		var increasing: [Int] = Array(repeating: 1, count: n);
		//list of decreasing subsequence
		var decreasing: [Int] = Array(repeating: 1, count: n);
		i = 1;
		// Find increasing bitonic subsequence
		// Outer loop execute through from 1..n
		while (i < n)
		{
			j = 0;
			// Range of inner loop from 0 to n
			while (j < i)
			{
				if (i  != j && arr[i] > arr[j] 
                    && increasing[i] < increasing[j] + 1)
				{
					increasing[i] = increasing[j] + 1;
				}
				j += 1;
			}
			i += 1;
		}
		i = n - 2;
		// Find longest decreasing subsequence
		// Right to left direction
		while (i >= 0)
		{
			j = n - 1;
			while (j > i)
			{
				if (arr[i] > arr[j] 
                    && decreasing[i] < decreasing[j] + 1)
				{
					decreasing[i] = decreasing[j] + 1;
				}
				j -= 1;
			}
			i -= 1;
		}
		i = 0;
		// Calculate resultant LSB
		while (i < n)
		{
			if (increasing[i] + decreasing[i] - 1 > max)
			{
				max = increasing[i] + decreasing[i] - 1;
			}
			i += 1;
		}
		// Display array elements
		print("\n Array ");
		self.printData(arr, n);
		// Display calculated result
		print(" Length of LBS ", max );
	}
}
func main()
{
	let task: BitonicSubsequence = BitonicSubsequence();
	// Given integer element
	let arr: [Int] = [6, 7, 1, 5, 3, 2, 4, 9, 3, 2, 8, 7];
	// Get the number of element
	let n: Int = arr.count;
	// Test
	// (6, 7, 5, 4, 3, 2)
	task.findLBS(arr, n);
}
main();

Output

 Array
   6   7   1   5   3   2   4   9   3   2   8   7
 Length of LBS  6
/*
  Kotlin Program 
  Longest Bitonic Subsequence
*/
class BitonicSubsequence
{
	// Display the  given array elements
	fun printData(arr: Array < Int > , n: Int): Unit
	{
		// Execute loop through by array length n
		var i: Int = 0;
		while (i < n)
		{
			print("  " + arr[i]);
			i += 1;
		}
		print("\n");
	}
	// This is find the length of longest bitonic subsequence
	fun findLBS(arr: Array < Int > , n: Int): Unit
	{
		if (n <= 0)
		{
			return;
		}
		// Loop controlling variable (i and j)
		var i: Int = 1;
		var j: Int ;
		// resulant sequence
		var max: Int = 1;
		// Define two auxiliary array of n integer elements
		// Initial assign one to each of auxiliary array
		// Because each element can be first element of bitonic sequence
		// List of incressing subsequence
		var increasing: Array < Int > = Array(n)
		{
			1
		};
		//list of decreasing subsequence
		var decreasing: Array < Int > = Array(n)
		{
			1
		};
		// Find increasing bitonic subsequence
		// Outer loop execute through from 1..n
		while (i < n)
		{
			j = 0;
			// Range of inner loop from 0 to n
			while (j < i)
			{
				if (i != j && arr[i] > arr[j] && increasing[i] < increasing[j] + 1)
				{
					increasing[i] = increasing[j] + 1;
				}
				j += 1;
			}
			i += 1;
		}
		i = n - 2;
		// Find longest decreasing subsequence
		// Right to left direction
		while (i >= 0)
		{
			j = n - 1;
			while (j > i)
			{
				if (arr[i] > arr[j] && decreasing[i] < decreasing[j] + 1)
				{
					decreasing[i] = decreasing[j] + 1;
				}
				j -= 1;
			}
			i -= 1;
		}
		i = 0;
		// Calculate resultant LSB
		while (i < n)
		{
			if (increasing[i] + decreasing[i] - 1 > max)
			{
				max = increasing[i] + decreasing[i] - 1;
			}
			i += 1;
		}
		// Display array elements
		print("\n Array \n");
		this.printData(arr, n);
		// Display calculated result
		print(" Length of LBS " + max + "\n");
	}
}
fun main(args: Array < String > ): Unit
{
	var task: BitonicSubsequence = BitonicSubsequence();
	// Given integer element
	var arr: Array < Int > = arrayOf(6, 7, 1, 5, 3, 2, 4, 9, 3, 2, 8, 7);
	// Get the number of element
	var n: Int = arr.count();
	// Test
	// (6, 7, 5, 4, 3, 2)
	task.findLBS(arr, n);
}

Output

 Array
  6  7  1  5  3  2  4  9  3  2  8  7
 Length of LBS 6
Implementing longest bitonic subsequence
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment