Redirecting to
NADOS


  Prev   Next

Longest Bitonic Subsequence







Wherever you go, no matter what the weather, always bring your own sunshine.
~Anthony J. D'Angelo

Longest Bitonic Subsequence

Welcome Back Reader!

In this article we will discuss about the next problem based on
"Dynamic Programming" i.e. "Longest Bitonic Subsequence".

Important Links : Problem Link, Question Video , Solution Video


Before you move any further, it is advised that you give this problem a fair try.

Let's jump to the problem.

Understanding the problem:

In this problem you are given a number n, representing the number of elements of the array. This n is followed by n numbers representing the contents of an array of length n.

All you are required to do is to print the length of the longest bitonic subsequence of the array.

Note: Bitonic subsequence begins with elements in increasing order, followed by elements in decreasing order.

For example:

Sample Input: 10 10 22 9 33 21 50 41 60 80 1

Sample Output: 7

How ?

As we can see that 10, 22, 33, 50, 60, 80, 1 is the longest Bitonic Subsequence; it increases from 10 to 80 and then decreases to 1. And since its length is 7, the output becomes 7.

For more clarity of the question, watch this part of the video.

Approach:
  • In this problem we need to calculate the length of the longest occurring bitonic subsequence in an array.
  • To solve this problem we will use the same trick, which we used while solving Longest Increasing Subsequence.
  • First of all, while travelling the array from left to right we will calculate the length of Increasing Subsequence corresponding to each element.
  • For example, in the sample input array, while travelling from left to right, for element 33, we will store the count as 3; corresponding to 33, which represents length of increasing subsequence (10, 22 and 33).
  • After completing the traversal from left to right, we will now traverse the array again but this time from right to left and this time we will store the length of decreasing subsequence corresponding to each element.
  • For example, in the sample input array, while travelling from right to left, for element 33, we will store the count as 3; corresponding to 33, which represents length of decreasing subsequence (33, 21 and 1).
  • Then we will again travel the array from left to right to calculate the length of bitonic subsequence, corresponding to each element by using the length of increasing subsequence and decreasing subsequence corresponding to that element.
  • For each element, we can calculate the length of bitonic subsequence as:

    • Length of bitonic subsequence = length of increasing subsequence + length of decreasing subsequence -1.

  • For example, for element 33, we have 3 as the length of both increasing subsequence (10, 22 and 33) and for decreasing subsequence (33, 21 and 1). So the length of the bitonic subsequence (10, 22, 33, 21, 9) for this point becomes 5 (3 + 3 - 1 = 5).
  • We basically subtract 1 because that particular element is counted twice, once in the length of increasing subsequence and then in the length of decreasing subsequence.
  • And while travelling the array last time i.e. for calculating the length of bitonic subsequence for each point, we will maintain a variable omax (Overall Maximum) which will store the length of longest bitonic subsequence so far.

    • For more clarity of this part, watch this part of the video.

    Let's try to code this!

    img
  • The above code snippet is used for calculating length of increasing subsequence for each element.
  • This is exactly the same as the code for calculating longest increasing subsequence. So if you have any doubt then please check out the video of the longest increasing subsequence.
    • img
    img
  • The above code snippet is used for calculating length of decreasing subsequence for each element.
  • This is almost the same as the code for calculating longest increasing subsequence.
  • The only change is that we need to run a reverse loop this time.
    • img
  • Now, we need to calculate the length of the longest subsequence.
  • For this we take a variable omax (overall maximum) and initialize it with 0 and
  • Then we run a for loop on the length of the array and we check if the length of the bitonic subsequence at each element, greater than omax.
  • If it is greater than we update omax.
  • When we come out of this for loop, omax will store the length of longest bitonic subsequence, which is our required result, so we simply print omax.

    • For more clarity of the code, watch this part of the video.

Complexities:
Time Complexity: O(n^2)

A nested for loop is used 2 times and a single for loop once, which condenses to O(n^2).

Space Complexity: O(n)

Two n sized arrays are used which condenses to O(n).

Complete Code:

import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] arr = new int[n]; for (int i = 0; i < arr.length; i++) { arr[i] = Integer.parseInt(br.readLine()); } int[] lis = new int[arr.length]; for(int i = 0; i < arr.length; i++){ Integer max = null; for(int j = 0; j < i; j++){ if(arr[j] <= arr[i]){ if(max == null || lis[j] > max){ max = lis[j]; } } } if(max != null){ lis[i] = max + 1; } else { lis[i] = 1; } } int[] lds = new int[arr.length]; for(int i = arr.length - 1; i >= 0; i--){ Integer max = null; for(int j = arr.length - 1; j > i; j--){ if(arr[j] <= arr[i]){ if(max == null || lds[j] > max){ max = lds[j]; } } } if(max != null){ lds[i] = max + 1; } else { lds[i] = 1; } } int omax = 0; for(int i = 0; i < arr.length; i++){ if(lis[i] + lds[i] - 1> omax){ omax = lis[i] + lds[i] - 1; } } System.out.println(omax); } }
java; true";

We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.

Trust me it will just get easier to understand after you have watched the solution video.

You can contact us via our website. Doubts, suggestions and feedback are always welcomed.

It is also advised that you follow the sequence of modules and questions which is there on our website.

Keep practicing more and more problems daily. Meditate enough on each step of each problem.

All the best for an exciting future!
Happy Coding!

Arrays
Dynamic Programming
Author: Nikita Aggarwal
 
Run
Id Name