Maximum Sum Subsequence
http://programmingpraxis.com/2010/12/03/maximum-sum-subsequence/
def max_subseq(xs): prev_max, cur_max = 0,0 for x in xs: tmp = x+prev_max if prev_max >= 0 else x cur_max = max(tmp, cur_max) prev_max = tmp return cur_max L=[31, -41, 59, 26, -53, 58, 97, -93, -23, 84] max_subseq(L)
scheme
(use gauche.collection) (define (max-subsequence xs) (match-let1 (x . xr) xs (values-ref (fold2 (lambda (x r prev-r) (let1 r* (if (positive? prev-r) (+ x prev-r) x) (values (max r r*) r*))) x x xr) 0))) (max-subsequence '(31 -41 59 26 -53 58 97 -93 -23 84)) ; => 187