c++ - 最长的递增和递减子序列(自上而下，带内存)

Question

问题 - 给定一个长度为 N 的整数数组 A，找到先递增后递减的最长子序列的长度。输入:[1, 11, 2, 10, 4, 5, 2, 1]

输出:6

解释:[1 2 10 4 2 1]是最长的子序列。

我写了一个自上而下的方法。我有五个参数 - vector A(包含序列)、起始索引(表示当前索引)、前一个值、大(表示当前子序列中的最大值)和 map(m) STL。

对于回溯方法，我有两种情况 -

1. 元素被排除 - 在这种情况下，我们移动到下一个元素(start+1)。 prev 和large 保持不变。

2. 包含元素 - 有两种情况

   a.如果当前值(A[start])大于 prev 并且 prev == large 那么情况就是这样 的递增序列。那么方程就变成 1 + LS(start+1, A[start], A[start]) 即 prev 成为当前元素(A[start])，最大元素也成为 A[start]。

   b.如果当前值 (A[start]) 小于前一个且当前值 (A[start]) < 大，则 这就是递减序列的情况。那么方程就变成 1 + LS(start+1, A[start], 大)，即 prev 成为当前元素(A[start])，并且最大元素保持不变，即 大。

基本案例 -

1. 如果当前索引不在数组中，即 start == end 则返回 0。

2. 如果序列先递减然后递增则返回 0。即 if(current> previous 和 previous < 最大值) then return 0。

这不是一种优化的方法，因为 map.find() 本身就是一个昂贵的操作。有人可以建议优化自上而下的内存方法吗？

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

不确定自上而下，但似乎我们可以使用经典的 LIS算法只是从“两侧”接近每个元素。下面的示例中，当我们从两个方向迭代时，每个元素分别位于最右边和最左边。我们可以看到长度为 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