The Heaviest Increasing Subsequence
Print the largest SUM of any strictly increasing subsequence.
1 101 2 3 100 4 5 -> 106 1 + 2 + 3 + 100
Note the answer is not built from the longest increasing subsequence, which here is
1 2 3 4 5 with a sum of 15. Optimising for length and optimising for sum are
different problems, and the best answer to one can be a poor answer to the other.
The recurrence is problem #452 with one substitution:
#452 dp[i] = 1 + max over j<i with a[j]<a[i] of dp[j]
this dp[i] = a[i] + max over j<i with a[j]<a[i] of dp[j]
Count the elements and you get the length; add them and you get the sum. Everything else is identical, and seeing that a whole family shares one skeleton is worth more than either individual answer.
Two details. dp[i] starts at a[i], not at 0, because the subsequence consisting
of a[i] alone is always valid. And the answer is the maximum over all i, not
dp[n-1], since the best subsequence need not end at the last element.
Negative values are allowed, so the answer may be negative. An all-negative input
answers with its LARGEST single element, since adding any other element only reduces
the sum, and that is why -1 -2 -3 answers -1.