单帧操作

普通解法：

二进制枚举所有位置选或者不选，然后按顺序模拟操作，并更新相应的答案，时间复杂度，因为要开一个辅助数组来进行模拟操作，所以空间复杂度

 vector<int> solve(int n, vector<int> a){
    assert(n <= 20);
    int t[20];
    vector<int> ans; ans.resize(n);
    for(int i = 0; i < n; ++i) ans[i] = 0;
    for(int mask = 1; mask < (1<<n); ++mask){
        int num = 0;
        for(int i = 0; i < n; ++i) t[i] = a[i];
        for(int i = 0; i < n; ++i){
            if(mask>>i&1){
                num++;
                int mx = a[i];
                if(i-1>=0) mx = max(mx, t[i-1]);
                if(i+1< n) mx = max(mx, t[i+1]);
                if(i-1>=0) t[i-1] = mx;
                if(i+1< n) t[i+1] = mx;
                t[i] = mx;
            }
        }
        int temp = 0;
        for(int i = 0; i < n; ++i) temp += t[i];
        ans[num-1] = max(ans[num-1], temp);
    }return ans;
}

最优解法：

考虑动态规划。
用表示考虑完前个数字,进行了次操作，在不考虑第个数字的情况下第个数字变成了的情况下整个序列的值最多增加多少。最后一维为0表示位置操作了，最后一维为1表示位置没有操作。
那么考虑前个位置进行次操作，第个位置为转移到->对前个位置进行次操作。

如果位置不进行操作，有两种转移：

1. 位置没有操作过，那么不会对位置造成任何影响，
2. 位置进行过操作，那么位置的数字和位置的数字一定是相等的（特殊考虑)。这个时候我们判断一下和的大小，如果是较大，那么位置会变成并增加的贡献，否则位置和位置的值都会变成(因为对位置进行过操作)，增加的贡献（对0特判）

如果位置进行操作，那么也有两种转移：

1. 位置没有操作过，那么对的操作只能影响位置，判断一下 和之间的关系并转移即可。
2. 位置进行过操作，那么对的操作可能会影响和两个位置。和上面不操作的分支2进行相同的讨论即可。
   因为要遍历数组进行递推，数组前2维与n相关，第3维，转移的过程是的，所以总的时间复杂度和空间复杂度都是

class Solution {
public:
    /**
     * 
     * @param n int整型 数字个数
     * @param a int整型vector 待操作序列
     * @return int整型vector
     */
    int dp[205][205][205][2];
vector<int> solve(int n, vector<int> a){
    int maxn = 205;
    int inf = 0x3f3f3f3f;
    int ans = 0;
    for(int i = 0; i < n; ++i) ans += a[i];
    for(int i = 0; i < maxn; ++i)
        for(int j = 0; j < maxn; ++j)
            for(int k = 0; k < maxn; ++k)
                dp[i][j][k][0] = dp[i][j][k][1] = -inf;
    dp[0][0][a[0]][0] = 0;
    dp[0][1][a[0]][1] = 0;
    for(int i = 0; i < n-1; ++i){
        for(int j = 0; j <= i+1; ++j){
            for(int x = a[i]; x < maxn; ++ x){
                //00
                dp[i+1][j][a[i+1]][0] = max(dp[i+1][j][a[i+1]][0], dp[i][j][x][0]);
                //01
                if(x > a[i+1]){
                    dp[i+1][j+1][x][1] = max(dp[i+1][j+1][x][1], dp[i][j][x][0] + x-a[i+1]);
                }else{
                    dp[i+1][j+1][a[i+1]][1] = max(dp[i+1][j+1][a[i+1]][1], dp[i][j][x][0]+a[i+1]-x);
                }
                //10
                if(x > a[i+1]){
                    dp[i+1][j][x][0] = max(dp[i+1][j][x][0], dp[i][j][x][1]+x-a[i+1]);
                }else{
                    dp[i+1][j][a[i+1]][0] = max(dp[i+1][j][a[i+1]][0], dp[i][j][x][1]+(a[i+1]-x)+(i+1>1)*(a[i+1]-x));
                }
                //11
                if(x > a[i+1]){
                    dp[i+1][j+1][x][1] = max(dp[i+1][j+1][x][1], dp[i][j][x][1]+x-a[i+1]);
                }else{
                    dp[i+1][j+1][a[i+1]][1] = max(dp[i+1][j+1][a[i+1]][1], dp[i][j][x][1]+(a[i+1]-x)+(i+1>1)*(a[i+1]-x));
                }
            }
        }
    }
    int mx = 0;
    for(int k = 1; k <= n; ++k){
        for(int i = 1; i < maxn; ++i)
            for(int j = 0; j < 2; ++j) mx = max(mx, dp[n-1][k][i][j]);
        a[k-1] = ans+mx;
    }
    return a;
}
};