Skip to content

Instantly share code, notes, and snippets.

@rorydriscoll
Created December 3, 2011 00:32
Show Gist options
  • Save rorydriscoll/1425513 to your computer and use it in GitHub Desktop.
Save rorydriscoll/1425513 to your computer and use it in GitHub Desktop.
Subset sum problem
var max_sum = -Inf, best_begin = 0, best_end = 0, cur_begin = 0, cur_sum = 0
for (i = 0; i < values.length; ++i)
# Add the current value into our working sum
cur_sum += values[i]
# Update the max sum if we beat it
if cur_sum > max_sum:
max_sum = cur_sum
best_begin = cur_begin
best_end = i + 1
# A positive number can only help us, so move along
if values[i] >= 0:
continue
# If the sum so far is stil a net win, then continue
if cur_sum >= 0:
continue
# Bad news - our working sum is a net loss, so ditch it!
cur_sum = 0
cur_begin = i + 1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment