最大交替子数组和

Submission

运行时间: 156 ms

内存: 28.9 MB

class Solution:
    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:
        accuNeg = accuPos = -inf
        res = -inf
        for n in nums:
            accuNeg, accuPos = -n+accuPos, n+max(0, accuNeg)
            res = max(res, accuNeg, accuPos)
        return res


        # S[pos][n] = nums[n] + max(0, S[neg][n-1])
        # S[neg][n] = -nums[n] + max(0, S[pos][n-1])

Explain

该题解使用动态规划的思路求解最大交替子数组和问题。定义两个变量 accuNeg 和 accuPos 分别表示当前位置结尾的最大负数和最大正数。对于每个位置，如果当前数是负数，就更新 accuNeg 为当前数加上前一个位置的 accuPos；如果当前数是正数，就更新 accuPos 为当前数加上前一个位置的 accuNeg 和 0 的较大值。最后，结果就是 accuNeg、accuPos 和当前结果 res 三者的最大值。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:
        accuNeg = accuPos = -inf  # 初始化当前位置结尾的最大负数和最大正数
        res = -inf  # 初始化结果为负无穷
        
        for n in nums:
            # 更新当前位置结尾的最大负数和最大正数
            accuNeg, accuPos = -n+accuPos, n+max(0, accuNeg)
            res = max(res, accuNeg, accuPos)  # 更新结果
        
        return res

        # 状态转移方程：
        # S[pos][n] = nums[n] + max(0, S[neg][n-1])
        # S[neg][n] = -nums[n] + max(0, S[pos][n-1])

Explore

这样做是为了确保当`accuNeg`为负值时不会减少`accuPos`的值。如果直接加上`accuNeg`，当`accuNeg`为负数时会降低`accuPos`的值，这与寻找最大交替子数组和的目标不符。使用`max(0, accuNeg)`确保只有当`accuNeg`为非负数，即之前有有效的负数和，才会对`accuPos`产生增加效果。

在题解代码中，`accuNeg`和`accuPos`初始设置为负无穷。对于数组中的第一个元素，无论它是正数还是负数，都会正常处理。当第一个元素是负数时，`accuNeg`会更新为该元素值与`accuPos`（即负无穷）的和，实际上就是第一个元素的值。当第一个元素是正数时，`accuPos`则更新为该元素的值。这样的处理确保了无论第一个元素的符号如何，都能正确初始化`accuNeg`和`accuPos`。

使用`-inf`作为初始化值是为了确保在更新`accuNeg`和`accuPos`时，任何实际的数字都会替代这个初始值。对于全是负数的数组，虽然`accuPos`可能始终为`-inf`，但`accuNeg`将逐步更新为数组中负数和更大的值。最终，`res`将选择`accuNeg`和`accuPos`中的最大值，确保即便数组全是负数，也能得到正确的最大交替子数组和。

代码实现中，`accuNeg`和`accuPos`的更新过程实际上就是状态转移方程的直接体现。`accuPos`的更新为`n + max(0, accuNeg)`对应方程`S[pos][n] = nums[n] + max(0, S[neg][n-1])`，而`accuNeg`的更新为`-n + accuPos`对应方程`S[neg][n] = -nums[n] + max(0, S[pos][n-1])`。这两个更新过程确保了每个位置的`accuNeg`和`accuPos`都是基于前一个位置的值进行计算，符合动态规划的特性。