最长递增和递减子序列（自顶向下带记忆）

Question

问题-给定一个长度为N的整数数组，求最长子序列的长度，该序列先增加后减少。投入:[1,11,2,10,4,5,2,1]

产出：6

说明:[1，210，4，21]是最长的子序列。

我写了一个自上而下的方法。我有五个参数--vector A（包含序列）、start index（表示当前索引）、previer value、large（表示当前子序列中的最大值）和map(m)stl。

对于回溯方法，我有两个案例-

>

元素被排除-在本例中，我们移到下一个元素(start+1)。prev和large保持不变。

元素-有两种情况

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

b.如果电流值(A[start])小于prev，而电流(A[start])<大，则这是递减序列的情况。然后方程变为1+LS(start+1，a[start]，lage)，即prev变为当前元素(a[start])，最大元素保持不变，即lage。

基本案例-

>

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

如果序列先递减后递增，则返回0。即，如果（当前>上一个和上一个<最大值），则返回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