Problem Statement:
I had recently seen a problem statement which was asking to find the length of the longest bitonic subsequence in a given array of positive integers. A bitonic subsequence is a subsequence which first increases and then decreases. Here's what went inside my head while solving the problem:
Initial thoughts about the problem:
A subsequence can be longest if the smaller subsequences it is made of are the longest for their respective lengths. For the bitonic property to satisfy, we need to find the optimum value for longest increasing subsequence plus the longest decreasing subsequence. Therefore, this problem statement satisfies both the required properties of dynamic programming:
The solution:
So, the first target as part of finding a solution to the above problem statement is to find the length of the longest increasing subsequence (lis). Then, the length of the longest decreasing subsequence (lds). A combination of both of these should give me the solution of longest bitonic subsequence length. Now, we don't know how to combine lis and lds. So, I thought what if I calculate both the values for each of the indices in the given array i.e. lis from start to an index i, lds from index (i + 1) to the end and i ranges from 0 to the length of the given array. So, this gives me a picture of the lengths of both lis and lds for each of the indices in the given array. If we can store the sum of these values and find out the maximum among the stored values, then that is the required solution of the problem statement of finding the length of longest bitonic subsequence in a given array.
Understanding the code:
If you see the GitHub code (link in the references section below), there are majorly two methods lis() and lds() which calculates the longest increasing subsequence length and the longest decreasing subsequence length for a given range. The lis() is calculated always from the index 0 to an index i and the lds() is calculated from after the index i in the given array. Both of these operations are done for all of the indices and from within another method lbs() which keeps track of the sum of the values of lis and lds lengths. Finally, getMax() returns the maximum value stored in an array given the array and the number of elements in it.
Testcases:
A set of five testcases are given to test the algorithm from the main function itself. The outputs for each of them are added in the top comment section of the file.
References:
1. https://github.com/pyav/labs/blob/master/algorithms/dynamic%20programming/LongestBitonicSubsequence.java
I had recently seen a problem statement which was asking to find the length of the longest bitonic subsequence in a given array of positive integers. A bitonic subsequence is a subsequence which first increases and then decreases. Here's what went inside my head while solving the problem:
Initial thoughts about the problem:
A subsequence can be longest if the smaller subsequences it is made of are the longest for their respective lengths. For the bitonic property to satisfy, we need to find the optimum value for longest increasing subsequence plus the longest decreasing subsequence. Therefore, this problem statement satisfies both the required properties of dynamic programming:
- Overlapping subproblems.
- Optimum substructure.
The solution:
So, the first target as part of finding a solution to the above problem statement is to find the length of the longest increasing subsequence (lis). Then, the length of the longest decreasing subsequence (lds). A combination of both of these should give me the solution of longest bitonic subsequence length. Now, we don't know how to combine lis and lds. So, I thought what if I calculate both the values for each of the indices in the given array i.e. lis from start to an index i, lds from index (i + 1) to the end and i ranges from 0 to the length of the given array. So, this gives me a picture of the lengths of both lis and lds for each of the indices in the given array. If we can store the sum of these values and find out the maximum among the stored values, then that is the required solution of the problem statement of finding the length of longest bitonic subsequence in a given array.
Understanding the code:
If you see the GitHub code (link in the references section below), there are majorly two methods lis() and lds() which calculates the longest increasing subsequence length and the longest decreasing subsequence length for a given range. The lis() is calculated always from the index 0 to an index i and the lds() is calculated from after the index i in the given array. Both of these operations are done for all of the indices and from within another method lbs() which keeps track of the sum of the values of lis and lds lengths. Finally, getMax() returns the maximum value stored in an array given the array and the number of elements in it.
Testcases:
A set of five testcases are given to test the algorithm from the main function itself. The outputs for each of them are added in the top comment section of the file.
References:
1. https://github.com/pyav/labs/blob/master/algorithms/dynamic%20programming/LongestBitonicSubsequence.java
No comments:
Post a Comment