nbnt001's blog

By nbnt001, history, 8 days 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

»
8 days 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.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh thanx, got it.

    • »
      »
      »
      8 days 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.

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 days 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.