最大连续子序列问题

题目

53. Maximum Subarray

解法

方法一

curSum为包含当前值的连续序列最大值，如对序列nums[:i]，curSum和中必定包含nums[i]。

    def maxSubArray(self, nums):
        curSum = maxSum = nums[0]
        for num in nums[1:]:
            curSum = max(num, curSum + num)
            maxSum = max(maxSum, curSum)
        return maxSum

思路相同，另一种更为简洁的写法

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

方法二

序列nums[k]可分为nums[0,1,...,s-1,s]和nums[s+1,s+2,...k-2,k-1]两部分。
我们可以轻易求出前半部分nums[:s]的值，则后部分nums[s+1:k]=nums[:k]-nums[:s]。

    def maxSubArray(self, nums) -> int:
        res = nums[0]
        msub = min(nums[0], 0)
        for i in range(1, len(nums)):
            new = nums[i - 1] + nums[i]
            res = max(new - msub, res, nums[i])
            msub = min(new, msub)
            nums[i] = new
        return res