nbnt001's blog

By nbnt001, history, 13 days ago,

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

• 0

 » 13 days ago, # | ← Rev. 4 →   +1 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.
•  » » 13 days ago, # ^ |   0 Oh thanx, got it.
•  » » » 13 days ago, # ^ | ← Rev. 2 →   +1 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.
•  » » » » 13 days ago, # ^ |   0 Yes, got it. That's why I deleted that comment. Thank you
•  » » 12 days ago, # ^ |   0 You can find prefix[i] and suffix[i] in $O(n\cdot \log n)$ time with a Data Structure like BIT, or with Binary Search.