https://leetcode.com/problems/maximum-subarray/editorial/
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution:
def maxSubArray(self, A: List[int]) -> int:
if not A:
return 0
N=len(A)
S=0
M=float('-inf')
for i in range(N):
S+=A[i]
M=max(M,S)
if S<0:
S=0
return M
|
divide and conquer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution:
def maxSubArray(self, A: List[int]) -> int:
def f(l,r):
if l>r:
return -math.inf
mid=(l+r)//2
lmax=0
curr=0
for i in range(mid-1,l-1,-1):
curr+=A[i]
lmax=max(curr,lmax)
rmax=0
curr=0
for i in range(mid+1,r+1):
curr+=A[i]
rmax=max(curr,rmax)
curr=lmax+rmax+A[mid]
left=f(l,mid-1)
right=f(mid+1,r)
return max(curr,left,right)
return f(0,len(A)-1)
|