leetcode 53. 最大子序和

发表于 更新于 分类于 阅读次数：

解题思路

定义f(i)：以第i个数结尾的连续子数组的最大和
答案即为：max(f(i)), 0<=i<n

f(i) = max(f(i-1)+num[i], num[i])

时间复杂度：O(n), 空间复杂度：O(1)

代码

1
2
3
4
5
6
7
8
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = nums[0]
        pre_max_sum = 0
        for num in nums:
            pre_max_sum = max(pre_max_sum + num, num)
            ans = max(pre_max_sum, ans)
        return ans