Skip to content

Instantly share code, notes, and snippets.

@shvechikov
Created October 9, 2015 08:26
Show Gist options
  • Save shvechikov/3f08b77457cc2abadaef to your computer and use it in GitHub Desktop.
Save shvechikov/3f08b77457cc2abadaef to your computer and use it in GitHub Desktop.
def find_best_subarray(array):
best_sum = 0
best_start = 0
best_end = 0
cur_sum = 0
cur_start = 0
cur_end = 0
for i, x in enumerate(array):
cur_end = i + 1
cur_sum += x
if cur_sum < 0:
cur_sum = 0
cur_start = i + 1
if cur_sum > best_sum:
best_sum = cur_sum
best_start = cur_start
best_end = cur_end
print('i = {:=2} x = {:=2} cur_sum = {:=2}'.format(i, x, cur_sum))
return best_sum, best_start, best_end
array = [-2, 1, -3, 4, -1, 2, 1, -5]
print('SOLUTION:')
print(find_best_subarray(array))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment