From charlesreid1

MVCS: Maximum value contiguous subsequence

Problem Description

Given a sequence of integers, a_1, a_2, \dots, a_n, determine the subsequence of integers with the maximum sum.

(Note, this problem is only interesting if there are negative numbers.)


This is a fairly straightforward dynamic programming problem that just requires evaluating the maximum sum for a sliding window, and store the results in a 1D array.