456. 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.
Constraints - `1 ≤ n ≤ 2000` - `-1000000 ≤ value ≤ 1000000`
Input
The first line contains an integer n.
The second line contains n space-separated integers.
Output
Print the largest sum of a strictly increasing subsequence.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.