7.23小红书题三题解

刚看LeeCode 恍然大悟 ，解法同 1746:经过一次操作后的最大子数组 状态DP

笔者使用 便利+贪心 超时，现在马后炮补一篇题解。

对于每一次查询

输入有：

len: 数组长度

x:替换的数字

nums :输入的数组

dp[i][0]表示到i为止，未使用替换得到的最大子数组和，

dp[i][1]表示到i为止，使用过一次替换后得到的最大子数组和

dp[i][0]=math.max(dp[i-1][0]+nums[i],nums[i])

dp[i][1]=math.max(dp[i-1][1]+nums[i],nums[i-1][0]+x)

res=Mathmax(math.max(dp[i][0],dp[i][1]),res)

而且应该使用滚动变量优化，在读入数组的时候就进行计算。

时间复杂度O(n)

空间复杂度O(1)

如有错误，还请指正