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)
{
// 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)
}
}``````

#### 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()
{
// 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)
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)
{
// 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)
}
}``````

#### 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()
{
// 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);
}
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()
{
// 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)
}
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() :
#  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)

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()
#  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)
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)
}
}``````

#### 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()
{
// 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)
}
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
{
// 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)
}``````

#### Output

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

## 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.

Categories
Relative Post