1186. 删除一次得到子数组最大和 (opens new window)

1.动态规划

定义dp[ i ][ k ]：表示以元素arr[i]结尾的子数组最大和，其中k代表两种状态，子数组选择删除或者不删除一个元素得到的最大和。

• dp[ i ][ 0 ]：当前最大和不删除元素，如果前一个dp[ i-1 ][ 0 ]的结果已经小于零，那么arr[i]没有必要与前面的子数组进行合并；如果大于零则可以进行合并。
• dp[ i ][ 1 ]：当前最大和需要删除一个元素，具体删除哪个元素需要分为两种情况：
  • 如果当前选择删除arr[i]，那么最大值为dp[ i ][ 1 ]=dp[ i-1 ][ 0 ]
  • 如果删除的是前面【0，i-1】之间的某个数，那么实际上并不需要我们再遍历一次进行求解，因为去掉的最小值实际上就是dp[i-1][1]中删掉的最小值，这样才能使dp[i-1][1]子数组和是最大的。因此最后最大值为dp[ i ][ 1 ]=dp[ i-1 ][ 1 ]+arr[i]

这里思考，为什么动规可以找到最大的元素？问题简化成如果都不考虑删除的条件下的子数组最大和。也就是说arr[i]和前面子数组合并时，有没有可能只合并子数组的右半部分？答案是不可能的，根据dp数组定义，前面计算得到的子数组和dp[i-1]无论从中间哪个位置劈开，左半部分一定都是大于0。因为如果小于零，则dp[i-1]显然可以只保留右半部分的结果更新最大子数组和。

子数组的“连续性”保证了最大和的连续性，从而保证了合并后arr[i]能够增加的子数组和，区间是最大的。在删除操作中，最然没有任何地方求最小值，但利用dp数组定义反过来推导出dp[ i-1 ][ 1 ]删除的就是最小值。

class Solution {
    public int maximumSum(int[] arr) {
        int[][] dp=new int[arr.length][2];
        dp[0][0]=arr[0];
        dp[0][1]=0;
        int res=arr[0];
        for(int i=1;i<arr.length;i++){
            //不删
            dp[i][0]=Math.max(arr[i],dp[i-1][0]+arr[i]);
            //删除时，要么还是删除前面的元素，要么删除当前元素
            dp[i][1]=Math.max(dp[i-1][1]+arr[i],dp[i-1][0]);
            res=Math.max(res,dp[i][0]);
            res=Math.max(res,dp[i][1]);
        }
        return res; 
    }
}