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.

Yes, got it. That's why I deleted that comment. Thank you

You can find

`prefix[i]`

and`suffix[i]`

in $$$O(n\cdot \log n)$$$ time with a Data Structure likeBIT, or withBinary Search.