Skip to content

Instantly share code, notes, and snippets.

@viveksyngh
Created July 27, 2015 19:24
Show Gist options
  • Save viveksyngh/43b6c3061485525e9d67 to your computer and use it in GitHub Desktop.
Save viveksyngh/43b6c3061485525e9d67 to your computer and use it in GitHub Desktop.
Function will return maximum sum of sub array of an array
def maxSubArray(A):
maxSumSoFar = 0
currentMaxSum = 0
for i in range(0, len(A)) :
currentMaxSum += A[i]
if currentMaxSum < 0 :
currentMaxSum = 0
if maxSumSoFar < currentMaxSum :
maxSumSoFar = currentMaxSum
if maxSumSoFar == 0 and max(A) >= 0 :
return 0
elif maxSumSoFar == 0 and max(A) < 0 :
return max(A)
else :
return maxSumSoFar
# For [−2,1,−3,4,−1,2,1,−5,4] value of A it will return -6
# For [-500] it will return -500
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment