DAY6 连续子数组最大和

剑指Offer 42：连续子数组最大和

Leetcode 53. Maximum Subarray

思路比较简单：从前往后累加，当累加和为负数则归零，重新累加；最大和取每次累加和中最大的值。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        max_sum = tmp_sum = nums[0]
        for i in range(1, len(nums)):
            tmp_sum = max(nums[i], nums[i] + tmp_sum)
            max_sum = max(max_sum, tmp_sum)
        return max_sum

另一个想法是用动态规划：设定f(n)为数组结尾为n的连续数组最大和

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。