Maximum Sum Increasing Subsequence
Find the maximum possible sum of a strictly increasing subsequence.
Input: the first line has N; the second line has the array.
Output: the maximum sum.
Constraints:
- 1 ≤ N ≤ 2000
- 1 ≤ ai ≤ 104
Sample Tests
Input 1
5 1 101 2 3 100
Output 1
106
Input 2
1 7
Output 2
7
Input 3
4 4 3 2 1
Output 3
4
Discussion (opens after you solve — no spoilers before)
No comments yet.