今日刷题 动态dp比较简单状态机模型

题目描述：1186. 删除一次得到子数组最大和

一个很好的题解，受益匪浅

比较通俗易懂的dp - 删除一次得到子数组最大和 - 力扣（LeetCode）：

我们定义f ( i ) 和 g ( i )，其中 f( i ) 表示不删除元素的情况下最大子数组和（以arr[i]结尾），g( i ) 代表删除元素的情况下的最大子数组和（以arr[i]结尾）。

f(i) = Math.max(f(i-1)+arr[i],arr[i]) //要么是当前元素累加之前的和，要么是重新从当前元素开始
g(i) = Math.max(g(i-1)+arr[i],f(i-1)) //要么是加上当前元素，也就是维持之前删除某个元素的情形，即g[i-1]+arr[i]//要么是删除当前这个元素，那么区间[0, i-1]就是不删除元素的情况，即f(i-1)+0（注意是f不是g！！）

问题在于初始化：

f(0)= arr[0] //因为必须要有元素，不能为 0 个元素

g(0) = 什么呢？

举个例子，假设我们要计算g(1)：

g(1) = Math.max(g(0)+arr[1],f(0))//题目提到至少保留一个元素，所以不可能是之前删过元素（g(0)+arr[1]），必须要选f(0)，即g(0)要足够小
// g(0) + arr[1] < arr[0]
// g(0) < arr[0] - arr[1]
// 因为 - 10^4 <= arr[i] <= 10^4，所以arr[0]-arr[1] >= -2 * 10^4，即g(0)取-20001即可

完整AC代码

class Solution {public int maximumSum(int[] arr) {int len=arr.length;int[] f=new int[len];int[] g=new int[len];int res=arr[0];f[0]=arr[0];g[0]=-20001;for(int i=1;i<len;i++){f[i]=Math.max(f[i-1]+arr[i],arr[i]);g[i]=Math.max(g[i-1]+arr[i],f[i-1]);//要么不删除当前元素即g[i-1]+arr[i]，要么删除当前元素即f[i-1]（只有一次删除机会，说明之前都没有删除过任何元素）res=Math.max(res,Math.max(f[i],g[i]));}return res;}
}