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.
1 class Solution(object): 2 def maxSubArray(self, nums): 3 thissum,maxsum = 0,-9999999999999 4 for v in nums: 5 thissum += v 6 if thissum>maxsum: 7 maxsum = thissum 8 if thissum<0: 9 thissum = 0 10 return maxsum
1 class Solution(object): 2 def maxSubArray(self, nums): 3 thissum=maxsum = nums[0] 4 for v in nums[1:]: 5 thissum = max(v,v+thissum) 6 maxsum = max(maxsum,thissum) 7 return maxsum
[leetcode DP]53. Maximum Subarray
原文：http://www.cnblogs.com/fcyworld/p/6538058.html