Given an unsorted array on integers, find the length of its largest sub-sequence such that it is increasing at first and then decreasing and the number of elements in increasing and decreasing parts should be the same.
Input: 1 2 3 2 1 4 5 6 7 19 15 12 10 9 Output: 9
An O(n^2) solution is to Maintain two arrays, prefix[i] and suffix[i], where prefix[i] gives me the longest increasing subsequence which ends at index i, and suffix[i] gives me the longest decreasing subsequence which starts at index i. Now just brute force all the indexes, and for each i, the answer is (2*min(prefix[i],suffix[i]))-1 and compute the maximum answer. Calculating prefix[] and suffix[] is an O(n^2) dp similar to the longest increasing subsequence.
Oh thanx, got it.
Sure, no problem. Just FYI, I have the min(prefix[i], suffix[i]) which takes care of the same length of the increasing and decreasing subsequences.
You can find
prefix[i]
andsuffix[i]
in $$$O(n\cdot \log n)$$$ time with a Data Structure like BIT, or with Binary Search.