nbnt001's blog

Need help solving this question. I know DP would be used but still, no idea. Thanx
By nbnt001, history, 4 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh thanx, got it.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like 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.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply