算法思想一：暴力枚举

解题思路：

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

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

注：由于此方法需要进行二进制枚举所有可能性，则最终时间复杂度较高会超时，此方法做了解即可

代码展示：

C++版本 

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 数字个数
     * @param a int整型vector 待操作序列
     * @return int整型vector
     */
     vector solve(int n, vector<int> a){
         vector res(n, 0);
         for(int i = 1; i < (1 << n); i++){ //枚举数字的可能性
             int num = 0;
             vector 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每次回归原来的数组

算法思想二：动态规划

解题思路：

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

设置两个dp，其中dp如是记录每次操作后的值，。而dp1是用来在bfs时找到当前操作的最大增加量，最后需要更新进dp中，dp1的更新方式类似的dp

代码展示：

JAVA版本 
import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 数字个数
     * @param a int整型一维数组 待操作序列
     * @return int整型一维数组
     */
    public int[] solve (int n, int[] a) {
        // write code here
        int[] ans = new int[n];
        // dp记录没次操作后的值
        int[][] dp = new int[n][201];
        // dp1用来在bfs找到当前操作的最大增加量
        int[][] dp1 = new int[n][201];
        // 初始化 dp dp1全都为 -1
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
            Arrays.fill(dp1[i], -1);
        }
        Queue<Sta> q = new LinkedList<>();
        int sum = 0;
        // 处理连续三个数
        for (int i = 0; i < n; ++i) {
            sum += a[i];
            int t = a[i], g = a[i], cnt = 1;
            if (i > 0) { // 非下界
                t = Math.max(a[i - 1], t);
                g += a[i - 1]; // 三个数的总值
                cnt++; // 三个元素个数
            }
            if (i < n - 1) { // 非上界
                t = Math.max(a[i + 1], t);
                g += a[i + 1];
                cnt++;
            }
            q.add(new Sta(i, 1, t));  // 放入队列进行bfs
            dp[i][t] = Math.max(dp[i][t], cnt * t - g);
            ans[0] = Math.max(cnt * t - g, ans[0]);
        }
        for (int k = 1; k < n; ++k) {
            int sz = q.size();
            for (int i = 0; i < sz; ++i) {   // 遍历找到最大增加量
                Sta sta = q.poll();
                assert sta != null;
                int pos = sta.pos, kk = sta.k, mx = sta.mx;
                for (int j = pos + 1; j < n; ++j) {  // 向后扩展 mx
                    int w, g, cnt = 2;//扩展状态
                    if (j == pos + 1) {
                        w = mx;
                        g = 2 * mx;
                    } else if (j == pos + 2) {
                        w = Math.max(mx, a[j]);
                        g = mx + a[j];
                    } else {
                        w = Math.max(a[j - 1], a[j]);
                        g = a[j - 1] + a[j];
                    }
                    if (j < n - 1) {
                        w = Math.max(a[j + 1], w);
                        g += a[j + 1];
                        cnt++;
                    }
                    if (dp1[j][w] == -1) q.add(new Sta(j, kk + 1, w));//保存状态
                    dp1[j][w] = Math.max(dp1[j][w], cnt * w - g + dp[pos][mx]);//更新结果
                    ans[kk] = Math.max(dp1[j][w], ans[kk]);
                }
                dp[pos][mx] = -1;//还原数组为-1，方便下一轮扩展用
            }
            int[][] temp = dp;
            dp = dp1;
            dp1 = temp;
  
        }
        for (int i = 0; i < n; i++) {
            ans[i] += sum;
        }
        return ans;
    }
    public class Sta {
        //pos是下标，k是第几次操作，mx当前连续三个的最大值
        int pos;
        int k;
        int mx;
  
        public Sta(int pos, int k, int mx) {
            this.pos = pos;
            this.k = k;
            this.mx = mx;
        }
    }
}
C++版本 
class Solution {
public:
    /**
     *
     * @param n int整型 数字个数
     * @param a int整型vector 待操作序列
     * @return int整型vector
     */
    
    vector<int> ans;
    struct Sta{ int pos, k, mx; };
    vector<int> solve(int n, vector<int>& a) {
        // write code here
        ans.resize(n, INT_MIN);
        int maxe = *max_element(a.begin(), a.end());
        vector<vector<int>> dp(201, vector<int>(201, -1)), dp1 = dp;
        queue<Sta> q;
        int sum = 0;
        for(int i = 0; i < n; ++i){
            sum += a[i];
            int t = a[i], g = a[i], cnt = 1;
            if(i > 0) t= max(a[i-1], t), g += a[i-1],cnt++;
            if(i < n - 1) t =max(a[i+1], t), g += a[i+1], cnt++;
            q.push({i, 1, t});
            dp[i][t]=max(dp[i][t], cnt*t-g);
            ans[0] = max(cnt*t-g, ans[0]);
        }
        for(int k = 1; k < n; ++k){
            int sz = q.size();
            for(int i = 0; i < sz; ++i){
                auto sta = q.front(); q.pop();
                int pos = sta.pos, kk = sta.k, mx = sta.mx;
                for(int j = pos+1; j < n; ++j){
                    int w, g, cnt = 2;//扩展状态
                    if(j == pos+1) w = mx, g = 2*mx;
                    else if(j == pos+2) w = max(mx, a[j]), g = mx+a[j];
                    else w = max(a[j-1],a[j]), g = a[j-1]+a[j];
                    if(j < n - 1) w = max(a[j+1], w), g += a[j+1], cnt++;
                    if(dp1[j][w]==-1) q.push(Sta{j, kk+1, w});//保存状态
                    dp1[j][w]=max(dp1[j][w], cnt*w-g+dp[pos][mx]);//更新结果
                    ans[kk] = max(dp1[j][w], ans[kk]);
                }
                dp[pos][mx] = -1;//还原数组为-1，方便下一轮扩展用
            }
            swap(dp, dp1);
        }
        for(auto &x : ans) x+=sum;
        return ans;
    }
};

复杂度分析

时间复杂度：，遍历dp矩阵时间
空间复杂度：，建立一个这样的矩阵

算法思想三：四维dp数组动态规划

解题思路：

方法三和方法二的主要思想都是一样的，只是在状态方程转移采用两种表现形式

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

如果位置 i+1 不进行操作，有两种转移：
1、位置 i 没有操作过，那么不会对位置 i+1 造成任何影响，
2、位置 i 进行过操作，那么 i-1 位置的数字和位置 i 的数字一定是相等的（特殊考虑 i=0)。这个时候我们判断一下 a(i+1)和 k 的大小，如果是 k 较大，那么 i+1 位置会变成 k 并增加 的贡献，否则位置 i 和位置 i-1 的值都会变成 a[i+1](因为对位置 i 进行过操作)，增加 的贡献（对0特判）
如果位置 i+1 进行操作，那么也有两种转移：
1、位置 i 没有操作过，那么对 i+1 的操作只能影响位置 i ，判断一下 a[i+1]和 k 之间的关系并转移即可。
2、位置 i 进行过操作，那么对 i+1 的操作可能会影响 i 和 i-1 两个位置。和上面 i+1 不操作的分支2进行相同的讨论即可。

代码展示：

C++版本 
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;
    }
};

复杂度分析

时间复杂度：，因为要遍历 dp 数组进行递推，数组前2维与n相关，第3维等于，转移的过程是的
空间复杂度：，建立一个这样的矩阵