53_MaximumSubarray.py

# coding: utf8


"""
    题目链接: https://leetcode.com/problems/maximum-subarray/description.
    题目描述:

    Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

    For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
    the contiguous subarray [4,-1,2,1] has the largest sum = 6.

    click to show more practice.

    More practice:
    If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which
    is more subtle.

"""


class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0

        return self.dynamic_sub_array(nums)

    # 动态规划, O(n)
    def dynamic_sub_array(self, nums):
        ans = float('-inf')
        cur = 0
        for i in range(len(nums)):
            cur += nums[i]
            ans = max(ans, cur)
            if cur < 0:
                cur = 0

        return ans