题解 | #单帧操作#

思路：

题目的主要信息：

• 给一串数组，每次找到一个位置进行一次操作：将该位置前后一个数及本身改为三者中的最大值
• 一共进行n次操作，每次操作需要找到改变后使数组和最大那个位置来改变

方法一：暴力解法（超时）
具体做法：
利用二进制掩码的特性，枚举所有位置选择或是不选择的组合（相当于n次操作，选择的位置进行排列足组合），按照顺序模拟改变的值，最后更新较大值即可。

class Solution {
public:
    vector<int> solve(int n, vector<int>& a) {
        vector<int> res(n, 0);
        for(int i = 1; i < (1 << n); i++){ //枚举数字的可能性
            int num = 0;
            vector<int> temp = a; //每次记录修改的数组
            for(int j = 0; j < n; j++){
                if((i >> j) & 1){
                    num++;
                    int maxnum = a[j];
                    //处理边界
                    if(j - 1 >= 0)
                        maxnum = max(maxnum, temp[j - 1]);
                    if(j + 1 < n)
                        maxnum = max(maxnum, temp[j + 1]);
                    if(j - 1 >= 0)
                        temp[j - 1] = maxnum;
                    if(j + 1 < n)
                        temp[j + 1] = maxnum;
                    temp[j] = maxnum;
                }
            }
            int sum = 0;
            for(int j = 0; j < n; j++)  //求和
                sum += temp[j];
            res[num - 1] = max(res[num - 1], sum);//更新
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，两个循环，外循环掩码自然是，内循环一次遍历
• 空间复杂度：，使用辅助数组temp每次回归原来的数组，res属于必要空间

方法二：动态规划
具体做法：
要求的最大值等于数组a的元素和加上每次操作后增加最多的大小。因此我们可以一开始就求出数组a的元素和，然后用辅助数组dp，代表每次操作位置后，处的值为时对应的最大总增量。
我们再借助队列做一个类似bfs的遍历，队列中记录的分别是元素下标、第几次操作、以当前元素为中的连续三个最大值。对于每次操作，从队列中取出元素，向后扩展，更新最大值。

我们设置两个dp，其中dp如图所示是记录每次操作后的值，初始时如图所示初始化。而dp1是用来在bfs时找到当前操作的最大增加量，最后需要更新进dp中，dp1的更新方式类似的dp，就不画图了。

class Solution {
public:
    struct S{ 
        int pos, k, mx; //pos是下标，k是第几次操作，mx当前连续三个的最大值
    };
    vector<int> solve(int n, vector<int>& a) {
        vector<int> res(n, INT_MIN);
        int maxe = *max_element(a.begin(), a.end()); //找到最大值
        //dp[i][j]代表每次操作i位置后，i处的值为j时对应的最大总增量
        vector<vector<int> > dp(n + 1, vector<int>(maxe + 1, -1));
        vector<vector<int> > dp1 = dp; //备份在这里供还原dp时使用
        queue<S> q;
        int sum = 0;
        for(int i = 0; i < n; i++){ //处理连续三个数
            sum += a[i];
            int mx = a[i], g = a[i], cnt = 1;
            if(i > 0){ //非下界
                mx = max(a[i - 1], mx);
                g += a[i - 1]; //这三个总值
                cnt++;  //这三个的元素个数，边界处没有三个
            }
            if(i < n - 1){ //非上界
                mx = max(a[i + 1], mx);
                g += a[i + 1];
                cnt++;
            }
            q.push(S{i, 1, mx});  //放入队列中方便bfs
            dp[i][mx] = max(dp[i][mx], cnt * mx - g); //更新增量最大
            res[0] = max(cnt * mx - g, res[0]);
        }
        for(int k = 1; k < n; k++){  //n次操作
            int sz = q.size();
            for(int i = 0; i < sz; i++){ //遍历找到最大增加量
                auto s = q.front();  //出队列
                q.pop();
                int pos = s.pos, kk = s.k, mx = s.mx;
                for(int j = pos + 1; j < n; j++){ //向后扩展mx
                    int mx2, g, cnt = 2;
                    if(j == pos + 1) { //左边
                        mx2 = mx; 
                        g = 2 * mx;
                    }
                    else if(j == pos + 2) {
                        mx2 = max(mx, a[j]);
                        g = mx + a[j];
                    }
                    else {
                        mx2 = max(a[j - 1], a[j]);
                        g = a[j - 1] + a[j];
                    }
                    if(j < n - 1){  //右边
                        mx2 = max(a[j + 1], mx2);
                        g += a[j + 1];
                        cnt++;
                    }
                    if(dp1[j][mx2] == -1) 
                        q.push({j, kk + 1, mx2});//保存状态
                    dp1[j][mx2] = max(dp1[j][mx2], cnt * mx2 - g + dp[pos][mx]);//更新结果
                    res[kk] = max(dp1[j][mx2], res[kk]);
                }
                dp[pos][mx] = -1;//还原数组为-1，方便下一轮扩展用
            }
            swap(dp, dp1);
        }
        for(int i = 0; i < n; i++) 
            res[i] += sum;
        return res;
    }
};

复杂度分析：

• 时间复杂度：，最坏情况为n次操作，每次相当于遍历dp矩阵
• 空间复杂度：，最大空间为矩阵的空间