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.)

Solution

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.

https://charlesreid1.com:3000/cs/java/src/master/dynamic-programming/max-val-seq

Flags