Maximum Sum Increasing Subsequence
mediumDynamic Programming II+20 XPTime limit 2s
A gamer's scores in n matches are listed in order. Pick some matches (keeping their order) so that the chosen scores are strictly increasing, and make the sum of the chosen scores as large as possible. (The longest such sequence is not always the one with the largest sum.)
Input:
- line 1:
n - line 2:
nscores
Output: the maximum possible sum.
Constraints: 1 ≤ n ≤ 2000, 1 ≤ score ≤ 10⁹. Use 64-bit integers for the sum.
Example: in 1 101 2 3 100 4 5 the answer is 1 + 2 + 3 + 100 = 106.
Think about it: this is LIS with sums instead of lengths: best[i] = a[i] + max(best[j]) over j < i with a[j] < a[i] (or just a[i] if there is none). The answer is the largest best[i]. O(n²). (A Fenwick tree over sorted values makes it O(n log n).)
Sample input 1
7 1 101 2 3 100 4 5
Sample output 1
106
Sample input 2
4 10 5 4 3
Sample output 2
10
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).