Problem: 1186. 删除一次得到子数组最大和

[TOC]

思路

动态规划

使用二维数组，一维数组里没个均含有不删除一个元素情况下的最大值，和删除了一个元素后的最大值，将着两个最大值进行对比，得到的就是答案的最大值；

递推关系为：

1
2
3
4
5
for(int i=1;i<n;i++){
    dp[i][0]=max(dp[i-1][0],0)+arr[i];
    dp[i][1]=max(dp[i-1][1]+arr[i],dp[i-1][0]);
    mx=max(mx,max(dp[i][0],dp[i][1]));
}

dp[i][0]确定以i为结尾的前i个子数组的最大和；
dp[i][1]确定删除一个元素（被删除的元素是现在这个为dp[i-1][0],被删除元素为之前的某一个为dp[i-1][1]+arr[i]）之后的前i个子数组的最大和。

确定以后与之前选取的最大值进行比较，选取现在值最大的数字

Code

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int maximumSum(vector<int>& arr) {
        int mx = arr[0];
        int n=arr.size();
        vector<vector<int>> dp(n,vector<int>(2,0));
        dp[0][0]=arr[0];
        dp[0][1]=0;
        for(int i=1;i<n;i++){
            dp[i][0]=max(dp[i-1][0],0)+arr[i];
            dp[i][1]=max(dp[i-1][1]+arr[i],dp[i-1][0]);
            mx=max(mx,max(dp[i][0],dp[i][1]));
        }
        return mx;
    }
};