Skip to content

Instantly share code, notes, and snippets.

@Strernd
Created Nov 11, 2015
Embed
What would you like to do?
import sys
def cross(X,Y):
l = sum = 0
for i in reversed(X):
sum = sum + i
if sum > l:
l = sum
r = sum = 0
for i in Y:
sum = sum + i
if sum > r:
r = sum
return l+r
def split(A):
h = len(A)/2
return A[:h], A[h:]
def max_sum(A):
if(len(A) < 1):
return 0
if(len(A)==1):
return A[0]
X,Y = split(A)
return max(max_sum(X),max_sum(Y),cross(X,Y))
print max_sum([31,-41,59,26,-53,58,97,-93,-23,84])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment