Q53 Maximum Subarray

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.

解题思路：

此题为动态规划中很经典的一个题目，具体做法是新建一个列表，记录最大子段和。如果子段和为负值或者子段和加上一个数负值，则重新开始计算子段和，否则，进行字段和的累加。最后，返回新建字段和列表中的最大值。时间复杂度为O(n)，空间复杂度也为O(n)。

Python实现：

# 动态规划
class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0 
        maxl = []  # 记录最大子段和
        maxl.append(nums[0])
        for i in range(1, len(nums)):
            if maxl[i-1] < 0 or maxl[i-1] + nums[i] < 0:  # 如果子段和为负值或者子段和加上一个数为负值，则把当前数作为下一个子段和的开始数值
                maxl.append(nums[i])
            else:  # 否则，累积子段和
                maxl.append(maxl[i-1] + nums[i])
        return max(maxl)

a = [-2,1,-3,4,-1,2,1,-5,4]
b = Solution()
print(b.maxSubArray(a))  # 6 # [4,-1,2,1]