42. 连续子数组的最大和

应用动态规划的思想

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        if not array:
            return 0
        cursum = 0
        greatestsum = float('-inf')
        for i in range(len(array)):
            if cursum <= 0:
                cursum = array[i]
            else:
                cursum += array[i]
            greatestsum = max(greatestsum, cursum)
        return greatestsum

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