题解 | #牛妹的面试#

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最大山峰序列长度
     * @param numberList int整型vector 给定的序列
     * @return int整型
     */
    int mountainSequence(vector<int>& numberList) {
        // write code here
        int N = numberList.size();
        if (N < 2) {
            return N;
        }
        vector<int> up(N,
                       0); //up[j]表示以j为最大值对应的标号的上升子序列长度
        vector<int> down(N,
                         0); //down[j]表示以j为最大值对应的标号的下降子序列的长度
        for (int j = 0; j < N; j++) {
            // 搜索左边
            if (j == 0) { //假如是第一个数，那直接设为1
                up[j] = 1;
            } else { //假如前面有数，那就要找到比自己小，且长度最长的那个标号
                int maxPath = 0;
                for (int i = j; i >= 0; i--) {
                    if (numberList[i] < numberList[j] &&
                            up[i] > maxPath) { //找到了比自己小且长度最长的数
                        maxPath = up[i];
                    }
                }
                up[j] += maxPath + 1;
            }
        }
        for (int j = N-1; j>=0 ; j--) {
            // 搜索右边
            if (j == N-1) { //假如是第一个数，那直接设为1
                down[j] = 1;
            } else { //假如后面有数，那就要找到比自己小，且长度最长的那个标号
                int maxPath = 0;
                for (int i = j; i<N ; i++) {
                    if (numberList[i] < numberList[j] &&
                            down[i] > maxPath) { //找到了比自己小且长度最长的数
                        maxPath = down[i];
                    }
                }
                down[j] += maxPath + 1;
            }
        }

        int maxRes = 0;
        for (int j = 0; j < N; j++) {
            for (int k = j; k < N; k++) {
                int temp = up[j] + down[k];
                if (numberList[k] == numberList[j]) { //俩数相等，需要减一
                    temp--;
                }
                if (temp > maxRes) {
                    maxRes = temp;
                }
            }
        }
        return maxRes;
    }
};

动态规划，up[j]表示以j为最大值对应的标号的上升子序列长度，down[j]表示以j为最大值对应的标号的下降子序列的长度

核心思想：以最大上升子序列为例，up[j]为 “数组值比自己小且长度最长的那个i”对应的up[i] 再+1