divide and conquer
class Solution(object):
def maxSubArray(self, A):
"""
:type nums: List[int]
:rtype: int
"""
def helper(A,left,right):
if left==right: return A[left]
middle=(left+right)/2
leftmax=helper(A,left,middle)
rightmax=helper(A,middle+1,right)
leftsuf=A[middle]
rightpref=A[middle+1]
temp=0
for i in reversed(range(left,middle+1)):
temp+=A[i]
if temp>leftsuf: leftsuf=temp
temp=0
for j in range(middle+1,right+1):
temp+=A[j]
if temp>rightpref: rightpref=temp
return max(leftmax,rightmax,leftsuf+rightpref)
return helper(A,0,len(A)-1)
class Solution(object):
def maxSubArray(self, A):
"""
:type nums: List[int]
:rtype: int
"""
local_max,global_max=0,0
for x in A:
local_max=max(x,x+local_max)
global_max=max(global_max,local_max)
return global_max
