Task

Given a sequence of integers, find a continuous subsequence which maximizes the sum of its elements, that is, the elements of no other single subsequence add up to a value larger than this one.



An empty subsequence is considered to have the sum of   0;   thus if all elements are negative, the result must be the empty sequence.




# Finds the subsequence of ary[1] to ary[len] with the greatest sum.
# Sets subseq[1] to subseq[n] and returns n. Also sets subseq["sum"].
# An empty subsequence has sum 0.
function maxsubseq(subseq, ary, len,    b, bp, bs, c, cp, i) {
	b = 0		# best sum
	c = 0		# current sum
	bp = 0		# position of best subsequence
	bn = 0		# length of best subsequence
	cp = 1		# position of current subsequence
 
	for (i = 1; i <= len; i++) {
		c += ary[i]
		if (c < 0) {
			c = 0
			cp = i + 1
		}
		if (c > b) {
			b = c
			bp = cp
			bn = i + 1 - cp
		}
	}
 
	for (i = 1; i <= bn; i++)
		subseq[i] = ary[bp + i - 1]
	subseq["sum"] = b
	return bn
}