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.

思路

这道题可以采用DP的方法来进行思考。遍历数组，访问每一个元素，计算当前元素之前的最大子数列(maximum subarray)的值。

利用两个变量来存储中间值，第一个变量final，存储的是当前的最大子数列(maximum subarray)的和，第二个变量sum，存储的是当前所有元素的非零和。

如果sum小于零，无论如何进行操作，后面的子数列(subarray)单独求和，要优于包含进之前元素的和。所以在计算sum的时候，如果和小于零，则置零。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sum = 0
        final = float("-inf")
        for i in nums:
            sum += i
            final = max(sum, final)
            if (sum < 0):
                sum = 0
        return final

这也是一道经典的问题，该问题最初由布朗大学的Ulf Grenander教授于1977年提出，当初他为了展示数字图像中一个简单的最大然似然估计模型。不久之后卡内基梅隆大学的Jay Kadane提出了该问题的线性算法。上面所用的解法就类似于Kadane算法。

参考：https://en.wikipedia.org/wiki/Maximum_subarray_problem

分治算法：http://xiadong.info/2016/08/leetcode-53-maximum-subarray/

https://discuss.leetcode.com/topic/426/how-to-solve-maximum-subarray-by-using-the-divide-and-conquer-approach/2

最大子数组问题详解：

http://www.cnblogs.com/zghaobac/p/3315719.html