03_最大子序和

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


# leetcode上的最优解
class Solution2(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sum = 0
        MaxSum = nums[0]
        for i in range(len(nums)):
            # sum += nums[i]
            sum = sum + nums[i]
            if sum > MaxSum:
                MaxSum = sum
            if sum < 0:
                sum = 0
        return MaxSum


# leetcode 上我能看懂的代码
class Solution3(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max_n = nums[0]
        for i in range(1, len(nums)):
            nums[i]= nums[i] + max(nums[i-1], 0)
            if nums[i]>max_n:
                max_n = nums[i]
        return max_n