Posted on by Kalkicode
Code Dynamic Programming

Longest Bitonic Subsequence

The Longest Bitonic Subsequence problem involves finding the length of the longest subsequence in an array that first increases and then decreases. A subsequence is a sequence of elements taken from the original array in the same order, but not necessarily consecutive. The Longest Bitonic Subsequence is a challenging problem that requires finding both increasing and decreasing subsequences within the array and then combining them to determine the longest possible subsequence.

Problem Statement

Given an array of integers, we need to find the length of the longest bitonic subsequence. A bitonic subsequence is a sequence that first increases and then decreases. For example, in the array [6, 7, 1, 5, 3, 2, 4, 9, 3, 2, 8, 7], the longest bitonic subsequence is [6, 7, 5, 4, 3, 2] with a length of 6.

Pseudocode Algorithm

Here is a step-by-step explanation of the algorithm to find the longest bitonic subsequence:


// Display the given array elements
printData(arr, n)
	
	// Find increasing bitonic subsequence
	for i = 1 to n:
		for j = 0 to i:
			if arr[i] > arr[j] and increasing[i] < increasing[j] + 1:
				increasing[i] = increasing[j] + 1
		
	// Find longest decreasing subsequence
	for i = n - 2 to 0:
		for j = n - 1 to i:
			if arr[i] > arr[j] and decreasing[i] < decreasing[j] + 1:
				decreasing[i] = decreasing[j] + 1
		
	// Calculate resultant LSB
	max = 1
	for i = 0 to n:
		if increasing[i] + decreasing[i] - 1 > max:
			max = increasing[i] + decreasing[i] - 1
		
	// Display array elements and calculated result
	printData(arr, n)
	print "Length of LBS: " + max

  

Code Solution

// 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

Explanation

The algorithm starts by initializing two auxiliary arrays, 'increasing' and 'decreasing', both with length n. These arrays will store the lengths of the increasing and decreasing subsequences ending at each index i of the original array.

The algorithm then finds the longest increasing subsequence in the array by comparing each element with the previous elements. If an element is greater than the previous element and the length of the increasing subsequence ending at the previous element plus one is greater than the current length, the length is updated.

Next, the algorithm finds the longest decreasing subsequence in the array by traversing the array from right to left. Similar to the previous step, if an element is greater than the next element and the length of the decreasing subsequence ending at the next element plus one is greater than the current length, the length is updated.

Finally, the algorithm calculates the length of the longest bitonic subsequence by iterating over the arrays 'increasing' and 'decreasing' and finding the maximum length when both increasing and decreasing subsequences are combined. The result is stored in the 'max' variable.

The array elements are then displayed, followed by the calculated result, which represents the length of the longest bitonic subsequence.

Resultant Output

The given array is [6, 7, 1, 5, 3, 2, 4, 9, 3, 2, 8, 7].

The length of the longest bitonic subsequence is 6.

Time Complexity

The time complexity of this algorithm is O(n^2) because we have two nested loops that iterate through the array of size n. The space complexity is O(n) since we use two auxiliary arrays of the same size as the input array.

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