Skip to content

Instantly share code, notes, and snippets.

@Strernd
Created November 11, 2015 18:31
Show Gist options
  • Save Strernd/155ec85192167463c5fe to your computer and use it in GitHub Desktop.
Save Strernd/155ec85192167463c5fe to your computer and use it in GitHub Desktop.
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