Dynamic Programming, Longest Bitonic SubSequence

Given an array, this function will find the length of the longest bitonic subarray in the given array.

Array is said to be bitonic if the elements in the array are first increasing and then decreasing. A sequence sorted in inccreasing order considerd bitonic with decreasing part as empty. Smilarly, a sequence sorted in deccreasing order considerd bitonic with increasing part as empty.

Example 1

INPUT  :
arr[] = {4, 7, 9, 20, 13}

OUTPUT :
5
The above array is bitonic as the elements are first increasing till 20 and then decreasing

Example 2

INPUT :
arr[] = {18, 8, 10, 15, 14, 13}

OUTPUT :
5
The longest bitonic subarray is of length 5 and the bitonic subarray is {8, 10, 15, 14, 13}

Time Complexity : O(n)

In this method the main idea is to maintain two arrays I[] and D[] using dynamic programming

a. I[i] stores the length of the longest increasing subarray from left to right ending at arr[i]

b. D[i] stores the length of the longest decreasing subarray from right to left starting at arr[i]

c. maximum length of the bitonic subarray is maximum of (I[i]+D[i]-1).

Algorithm

1. Create two arrays I[] and D[] dynamically ie, int *I = new int[n], int *D = new int[n] .Initialize I[0] to 1 and D[n-1] to 1

2. Computing values in I[] array
    a. Till end of the array ie, i=1 to n, if arr[i] > arr[i-1] then I[i] = I[i-1] + 1.
    else, I[i] = 1

3. Computing values in D[] array
    a. From the end of the array ie, i = n-2 till i =0, if arr[i] > arr[i+1] then D[i] = D[i    +1] +1
    else, D[i] = 1

4. Find the maximum of I[i] + D[i] -1, it is the length of the longest bitonic subarray.

C++ Program

#include <bits/stdc++.h>
using namespace std;

int longestBitonic(int arr[], int n)
{
	int* I = new int[n];
	int* D = new int[n];
	int length = 0;
	int subarray_start =0, subarray_end = 0;
	for (int i = 1; i < n; ++i) //constructing array I[]
	{
		I[0] = 1;
		if(arr[i]>arr[i-1])
		{
			I[i] = I[i-1] + 1;
		}
		else
		{
			I[i] = 1;
		}
	}
	for (int i = n-2; i >=0; --i) //constructing array D[]
	{
		D[n-1] = 1;
		if(arr[i] > arr[i+1])
		{
			D[i] = D[i+1] +1;	
		}
		else
		{
			D[i] = 1;
		}
	}
	for (int i = 0; i < n; ++i) //finding maximum length
	{
		if(I[i] + D[i] -1 > length)
		{
			length = I[i] + D[i] -1;
			subarray_start = i - I[i] +1;
			subarray_end = i + D[i] -1;
		}

	}
	cout<<"The length of the longest bitonic subarray is "<<length<<endl;
	cout<<"The longest bitonic subarray is from index "<<subarray_start<<" to index "<<subarray_end<<endl;

}
int main()
{
	int arr[]= {18, 8, 10, 15, 14, 13};  //creating an array
	int n = sizeof(arr)/sizeof(arr[0]); //size of the array
	longestBitonic(arr, n);
	return 0;
}
Try It

 


< Prev
Scroll to Top