A royalty ledger lists n payout amounts in chronological order. You want to select a subsequence of payouts (not necessarily adjacent), keeping them in chronological order, whose amounts are strictly increasing, so as to maximize the total selected amount. The selected subsequence must be non-empty (a single payout is allowed). Amounts may be negative. Report the maximum achievable total.
Line 1: an integer n.
Line 2: n space-separated integers, the payout amounts in chronological order.
A single integer: the maximum sum of a strictly increasing subsequence.
Example 1
Input
5 1 100 2 3 4
Expected
101
Explanation
The strictly increasing subsequence 1, 100 totals 101, which beats 1, 2, 3, 4 (total 10); so the maximum is 101.
Example 2
Input
4 -5 -2 -8 -1
Expected
-1
Explanation
Amounts are all negative. The best strictly increasing subsequence is the single largest amount, -1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →