Subset sum problem

SubsetSum

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