python最大子序和

迭代

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        L = len(nums)
        if L==1:
            return nums[0]
        maxval = nums[0]
        for i in range(L):
            temp = nums[i] #子序列从第i个数开始
            if temp >maxval:
                maxval = temp #第i个数大于先前求得的最大子序列和
            for j in range(i+1,L):
                if temp < 0: #当前子序列<0，舍弃
                    break
                temp += nums[j] #否则加上第j个数的值
                if temp > maxval:
                    maxval = temp#当前序列和大于先前求得的最大子序列和

        return maxval

可以得到正确结果，但在leetcode中会超时

动态规划

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        L = len(nums)
        if L==1:
            return nums[0]
        maxSAValue = before = nums[0]
        for num in nums[1:]:
            before = max(num,before+num)
            if before > maxSAValue:
                maxSAValue = before

        return maxSAValue

参考了一个大佬的想法，状态：dp[i]表示以第i个数结尾的最大子序列和。为了减少内存使用，只保存前一个数的值before和最大值maxSAValue就可