难度: Medium
Submission
运行时间: 168 ms
内存: 27.0 MB
class Solution:
def maxSumAfterOperation(self, nums: List[int]) -> int:
maxVal = -inf
dp0, dp1 = 0, -inf
for x in nums:
dp0, dp1 = max(dp0 + x, 0), max(dp1 + x, dp0 + x * x)
if dp1 > maxVal: maxVal = dp1
return maxVal
Explain
该题解采用了动态规划的方法来求解最大子数组和的问题，在此基础上加入了一次平方操作的变体。具体地，使用两个状态变量 dp0 和 dp1 分别代表不使用平方操作和使用一次平方操作的最大子数组和的情况： 1. dp0 表示当前位置 i 不使用平方操作的最大子数组和，其状态转移方程为 dp0 = max(dp0 + x, 0)，即考虑当前元素加入前一个子数组或者从当前元素开始新的子数组。 2. dp1 表示当前位置 i 使用了一次平方操作的最大子数组和，其状态转移方程为 dp1 = max(dp1 + x, dp0 + x * x)，即考虑当前元素加入前一个已经使用了平方操作的子数组，或者在当前元素使用平方操作并加入之前没有使用平方操作的子数组。 循环遍历数组中的每一个元素，更新这两个状态，并实时维护一个全局最大值 maxVal，最终返回 maxVal。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def maxSumAfterOperation(self, nums: List[int]) -> int:
maxVal = -inf # 初始化最大值为负无穷
dp0, dp1 = 0, -inf # 初始化不使用平方和使用一次平方的最大子数组和
for x in nums: # 遍历数组元素
dp0, dp1 = max(dp0 + x, 0), max(dp1 + x, dp0 + x * x) # 更新状态
if dp1 > maxVal: maxVal = dp1 # 更新全局最大值
return maxVal # 返回最终的最大值
Explore
`dp0`被初始化为0，这是因为`dp0`表示不使用平方操作的最大子数组和，如果数组的开头是负数，则可能不包含任何元素的子数组（即子数组和为0）是最优的。`dp1`被初始化为负无穷，因为它表示至少使用一次平方操作的最大子数组和，初始时因为没有元素被处理过，所以初始值设为最小可能值，表示不可达的状态。
状态转移公式`dp1 = max(dp1 + x, dp0 + x * x)`考虑了两种情况：1. `dp1 + x`代表当前元素`x`加入到已经使用过平方操作的子数组中；2. `dp0 + x * x`代表在当前元素`x`处使用平方操作，并将此元素加入到之前没有使用过平方操作的子数组中。这确保了`dp1`总是记录使用了一次平方操作的最大子数组和。
使用`max(dp0 + x, 0)`的设计允许算法在遇到负数累加导致总和减小的情况下，重置子数组的开始位置。这意味着如果当前累加的子数组和变为负数，不如从当前位置重新开始（子数组和重置为0），这有助于避免负数的累加拖累总和。
实时维护全局最大值`maxVal`是因为`dp1`记录的是使用一次平方操作的最大子数组和，这个最大值可能在数组的任何位置出现，并随着数组的进一步遍历而改变。如果仅在遍历结束后从`dp0`或`dp1`中选择最大值，可能会错过真正的最大值，特别是在`dp1`可能在数组的中间达到峰值，而后又因为负数的加入而减小。