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.
这个一道非常经典的题目，剑指offer上也有。
用DP做思路是最优的，但是DP的做法本身有很多种解释。一种是用f[i]表示以第i 个元素结尾的子数组的最大和。最后的最大和为max(f[i])。
另外一种解释是使用local, global的解法，即我们的f[i]是local, maxsum为global.
其实是用后一种解释更加合理，两种解释的代码也很相同，代码如下：
class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ if not nums: return 0 res = [0] * (len(nums)+1) maxsum = -sys.maxint-1 for i in xrange(1, len(nums)+1): if res[i-1] <= 0: res[i] = nums[i-1] else: res[i] = res[i-1] + nums[i-1] maxsum = max(maxsum, res[i]) return maxsum
另外一种解释是：
class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ if not nums: return 0 Local = nums[0] Global= nums[0] for i in xrange(1, len(nums)): Local = max(Local + nums[i], nums[i]) Global = max(Local, Global) return Global
原文：http://www.cnblogs.com/sherylwang/p/5628176.html