力扣 Hot100 普通数组经典题目 Python 实现

53. 最大子数组和

• 思路 1：前缀和。
• 代码

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        preSum = [0] * (len(nums) + 1)
        for idx, n in enumerate(nums):
            preSum[idx+1] = preSum[idx] + n
        res = float('-inf')
        for idx, p in enumerate(preSum):
            for i in range(idx):
                res = max(res, p - preSum[i])
        return res

优化后的前缀和实现（维护最小前缀和）：

class Solution:
    def maxSubArray(self, nums):
        if len(nums) == 1:
            return nums[0]
        res = float('-inf')
        preSum = 0
        minPreSum = 0
        for n in nums:
            preSum += n
            res = (res, preSum - minPreSum)
            minPreSum = (minPreSum, preSum)
         res