Skills101
← All coding problems

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: n scores

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).

Loading editor…

Log in to run and submit your code — it's free.