79. LeetCode.53. 最大子序和

• 标签： 动态规划
• 难度： 简单

---

• 题目描述

• 解法

遍历 nums 数组， 假设到了 i 位置， 用 s 记录 包含 nums[i] 的连续序列中的最大序列和, 若 nums[i] < 0, 则 s_i = nums[i], 否则 s_i = s_(i-1) + nums[i] ； 用 ms 记录从 nums[0] 到 nums[i] 之内的具有最大和的连续子序的和，ms_i = max(s_i, ms_(i-1)).

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        s,ms = nums[0], nums[0]
        for i in range(1, len(nums)):
            if s < 0:
                s = nums[i]
            else:
                s += nums[i]
            ms = max(s, ms)
        return ms
        

• 其他解法

暂略。