Longest Increasing and Decreasing subsequence (Top-Down with memoization)

Question

Question - Given an array of integers, A of length N, find the length of longest subsequence which is first increasing then decreasing. Input:[1, 11, 2, 10, 4, 5, 2, 1]

Output: 6

Explanation:[1 2 10 4 2 1] is the longest subsequence.

I wrote a top-down approach. I have five arguments - vector A(containing the sequence), start index(denoting the current index), previous value, large(denoting maximum value in current subsequence) and map(m) STL.

For the backtrack approach I have two cases -

element is excluded - In this case we move to next element(start+1). prev and large remains same.
element is included - having two cases

a. if current value(A[start]) is greater than prev and prev == large then this is the case of increasing sequence. Then equation becomes 1 + LS(start+1, A[start], A[start]) i.e. prev becomes current element(A[start]) and largest element also becomes A[start].

b. if current value (A[start]) is lesser than prev and current (A[start]) < large then this is the case of decreasing sequence. Then equation becomes 1 + LS(start+1, A[start], large) i.e. prev becomes current element(A[start]) and largest element remains same i.e. large.

Base Cases -

if current index is out of the array i.e. start == end then return 0.
if sequence is decreasing and then increasing then return 0. i.e. if(current> previous and previous < maximum value) then return 0.

This is not an optimized approach approach as map.find() is itself a costly operation. Can someone suggest optimized top-down approach with memoization.

int LS(const vector<int> &A, int start, int end, int prev, int large, map<string, int>&m){

    if(start == end){return 0;}
    if(A[start] > prev && prev < large){
        return 0;
    }

    string key = to_string(start) + '|' + to_string(prev) + '|' + to_string(large);

    if(m.find(key) == m.end()){
        int excl = LS(A, start+1, end, prev, large, m);
        int incl = 0;
        if(((A[start] > prev)&&(prev==large))){
            incl = 1 + LS(A, start+1, end, A[start],A[start], m); 
        }else if(((A[start]<prev)&&(A[start]<large))){
            incl = 1+ LS(A, start+1, end, A[start], large, m);
        }  

        m[key] = max(incl, excl);
    }

    return m[key];
}

int Solution::longestSubsequenceLength(const vector<int> &A) {
        map<string, int>m;
        return LS(A, 0, A.size(), INT_MIN, INT_MIN, m);
}

גלעד ברקן · Answer 1 · 2020-03-18T04:55:56.597

0

Not sure about top-down but it seems we could use the classic LIS algorithm to just approach each element from "both sides" as it were. Here's the example with each element as the rightmost and leftmost, respectively, as we iterate from both directions. We can see three instances of a valid sequence of length 6:

[1, 11, 2, 10, 4, 5, 2, 1]

 1 11       11 10 4 2 1
 1 2                2 1
 1 2 10        10 4 2 1
 1 2 4            4 2 1
 1 2 4 5          5 2 1
 1 2                2 1

edited Mar 18 '20 at 04:55

answered Mar 18 '20 at 04:49

גלעד ברקן

23,602
3
25
61

Thanks for the attempt. Actually what I am thinking is that there may be a solution where we reduce arguments to 2 then in that case 2D array memoization will work in time limits. For example - finding longest increasing and longest decreasing subsequence and performing some mathematical operation may help in getting the answer. Then in that case LIS and LDS will have 2 arguments only. – utkarsh bajpai Mar 18 '20 at 12:46

Longest Increasing and Decreasing subsequence (Top-Down with memoization)

1 Answers1