The maximum subarray
Solutions We have two similar tasks:
find the maximum sum of any nonempty subarray find the maximum sum of any nonempty subsequence The latter is clearly esier since the elements in a subsequence are not necessarily contiguous. The former is a very classical problem that we’ll deal with in a moment.
To solve the first task, we can sum all the positive elements. This works as long as we have at least one positive (or zero) element.
[Read More]