In [35]:
def max_crossing_subarray(A, start, mid, end):
cstart = mid
clsum = -10000000
csum = 0
i = mid
while i >= start:
csum += A[i]
if csum > clsum:
clsum = csum
cstart = i
i -= 1
cend = mid+1
crsum = -10000000
csum = 0
i = mid+1
while i <= end:
csum += A[i]
if csum > crsum:
crsum = csum
cend = i
i += 1
return (cstart, cend, clsum+crsum)
def max_subarray(A, start, end):
if start == end:
return (start, end, A[start])
else:
mid = start + int((end-start)/2)
lstart, lend, lsum = max_subarray(A, start, mid)
rstart, rend, rsum = max_subarray(A, mid+1, end)
cstart, cend, csum = max_crossing_subarray(A, start, mid, end)
if lsum >= rsum and lsum >= csum:
return (lstart, lend, lsum)
elif rsum>=lsum and rsum>=csum:
return (rstart, rend, rsum)
else:
return (cstart, cend, csum)
In [63]:
A = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
A = [-3, -25, -3, -16, -23]
max_subarray(A, 0, len(A)-1)
Out[63]:
In [67]:
def n2_max_subarray(A):
maxo = -100000000
s = 0
e = 0
for i in range(len(A)):
sumi = 0
for j in range(i, len(A)):
sumi += A[j]
if sumi >= maxo:
maxo=sumi
s = i
e = j
return (s, e, maxo)
n2_max_subarray(A)
Out[67]:
In [68]:
def n_max_subarray(A):
maxo = -10000000
starto = 0
endo = 0
sumi = -10000000
for i in range(len(A)):
endi = i
if sumi > 0:
sumi += A[i]
else:
sumi = A[i]
starti = i
if sumi > maxo:
maxo = sumi
starto = starti
endo = endi
return (starto, endo, maxo)
In [69]:
n_max_subarray(A)
Out[69]:
In [ ]: