#include <vector>
class Solution {
  public:
    /**
     * 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
     *
     * 返回最大山峰序列長度
     * @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) { //假如是第一個數(shù)，那直接設(shè)為1
                up[j] = 1;
            } else { //假如前面有數(shù)，那就要找到比自己小，且長度最長的那個標號
                int maxPath = 0;
                for (int i = j; i >= 0; i--) {
                    if (numberList[i] < numberList[j] &&
                            up[i] > maxPath) { //找到了比自己小且長度最長的數(shù)
                        maxPath = up[i];
                    }
                }
                up[j] += maxPath + 1;
            }
        }
        for (int j = N-1; j>=0 ; j--) {
            // 搜索右邊
            if (j == N-1) { //假如是第一個數(shù)，那直接設(shè)為1
                down[j] = 1;
            } else { //假如后面有數(shù)，那就要找到比自己小，且長度最長的那個標號
                int maxPath = 0;
                for (int i = j; i<N ; i++) {
                    if (numberList[i] < numberList[j] &&
                            down[i] > maxPath) { //找到了比自己小且長度最長的數(shù)
                        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]) { //倆數(shù)相等，需要減一
                    temp--;
                }
                if (temp > maxRes) {
                    maxRes = temp;
                }
            }
        }
        return maxRes;
    }
};

動態(tài)規(guī)劃，up[j]表示以j為最大值對應的標號的上升子序列長度，down[j]表示以j為最大值對應的標號的下降子序列的長度

核心思想：以最大上升子序列為例，up[j]為 “數(shù)組值比自己小且長度最長的那個i”對應的up[i] 再+1