最大子序和 動态規劃

解法一

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），傳回其最大和。

def maxSubArray(nums):
    length = len(nums)
    for i in range(1, length):
        # 目前值的大小與前面的值之和比較，若目前值更大，則取目前值，舍棄前面的值之和
        subMaxSum = max(nums[i] + nums[i - 1], nums[i])
        nums[i] = subMaxSum  # 将目前和最大的賦給nums[i]，新的nums存儲的為和值
    return max(nums)


alist=[-2,1,-3,4,-1,2,1,-5,4]
print(maxSubArray(alist))      

解法二

def maxSubArray( nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    # onesum維護目前的和
    onesum = 0
    maxsum = nums[0]
    for i in range(len(nums)):
        onesum += nums[i]
        maxsum = max(maxsum, onesum)
        # 出現onesum<0的情況，就設為0，重新累積和
        if onesum < 0:
            onesum = 0
    return maxsum


alist=[-2,1,-3,4,-1,2,1,-5,4]
print(alist)
print(maxSubArray(alist))