Skip to content

Instantly share code, notes, and snippets.

@viveksyngh
Created July 24, 2015 21:41
Show Gist options
  • Save viveksyngh/3ce56f4da4d8d9d92d83 to your computer and use it in GitHub Desktop.
Save viveksyngh/3ce56f4da4d8d9d92d83 to your computer and use it in GitHub Desktop.
Function will return Non Negative subarray with maximum sum
def maxset(self, A):
maxSum = 0
curretMaxSum = 0
maxStart = 0
maxEnd = 0
currentStart = 0
for i in range(len(A)) :
if A[i] >= 0 :
curretMaxSum += A[i]
if curretMaxSum > maxSum :
maxSum = curretMaxSum
maxStart = currentStart
maxEnd = i+1
elif curretMaxSum == maxSum :
if (i - currentStart + 1) > (maxEnd - maxStart +1) :
maxStart = currentStart
maxEnd = i + 1
if A[i] < 0 :
curretMaxSum = 0
currentStart = i + 1
return A[maxStart : maxEnd]
#Function will return Non Negative subarray with maximum sum
#If there is tie then longest subarray should be returned
print(maxset([1, 2, 3, -1, 2, 3])) # will return [1, 2, 3]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment