会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
题目要求我们在最多修改一个元素的条件下，计算数组的最大子段和。修改操作是将某一块田地的收益值变为给定的 v，也可以不修改。
问题可以分解为两种情况的较大值：
- 不修改：直接计算原数组的最大子段和（经典 Kadane 算法，注意子段非空）。
- 修改某个位置
i：将 a[i] 变为 v，此时包含该位置的最大子段和可以分为三部分：左侧以 i-1 结尾的最大子段和（如果为正就加上，否则不加）、修改后的值 v、右侧以 i+1 开头的最大子段和（如果为正就加上，否则不加）。即：
candidate[i] = max(0, left_max[i-1]) + v + max(0, right_max[i+1])
