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.
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.
--
一维DP, O(n).
假设A(0, i)区间存在k，使得[k, i]区间是以i结尾区间的最大值， 定义为Max[i], 在这里，当求取Max[i+1]时，
if (Max[i] + A[i+1] >0)
Max[i+1] = Max[i] + A[i+1]
if(Max[i]+A[i+1] <0) #也就是要舍弃
Max[i+1] = 0
'''
Created on Nov 13, 2014
@author: ScottGu<gu.kai.66@gmail.com, 150316990@qq.com>
'''
class Solution:
# @param A, a list of integers
# @return an integer
def maxSubArray(self, A):
sum=0
max=-655356
for x in A:
sum+=x
if(sum>max):
max=sum
if(sum<0):
sum=0
return max