SUB1 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

Dynamic programming

PROBLEM:

Define f(A) as the largest integer M such that [1, 2, \ldots,M] appears as a subsequence of A.

Given an array A, compute the maximum possible sum of f(A_1) + \ldots + f(A_K) such that A_1 + \ldots + A_K = A.
You can choose K.

EXPLANATION:

We’ll call f(B) the score of B.

We want to partition A into several subarrays and maximize the sum of their scores.
Suppose we pick the partition [l_1, r_1], [l_2, r_2], \ldots, [l_K,r_K] where:

  • l_1 = 1 and r_K = N
  • l_i = r_{i-1} + 1 for each valid i.

Let M_i = f(A[l_i, r_i]) be the score of the i-th subarray.
Then, we can always assume that each subarray ends as soon as it attains a score of M_i.
That is, the first subarray ends as soon as [1, 2, \ldots, M_1] appears as a subsequence, then the second one ends as soon as [1, 2, \ldots, M_2] appears as a subsequence, and so on.

This is easy to prove: suppose the first subarray ended later; then we could just shorten it and extend the second subarray instead, which doesn’t make the score of either subarray worse.
Doing this repeatedly will give us the conclusion above.

Note that doing this shrinking could technically leave us with some suffix of elements that are not in any of the K subarrays (since we might shrink r_K down to below N.)
However, we can simply take this suffix as a (K+1)-th subarray with score 0 and there’s no issue.

Using this observation, let’s try to compute the answer.

We use dynamic programming.
Define dp_i to be the maximum possible sum of scores when partitioning the first i elements of A, such that the last subarray ends at index i (and hence has a score of A_i).

Also let dp_0 = 0.

We then have the following:

  • If A_i = 1, then the previous subarray could’ve ended anywhere earlier.
    So, we simply obtain
    dp_i = 1 + \max(dp_0, dp_1, \ldots, dp_{i-1})
  • If A_i \gt 1 then we need to ensure that 1, 2, \ldots, A_i all appear in order, ending at index i.
    One way to think of this is: we can choose an index j \lt i such that A_j = A_i - 1, and then extend the subarray ending at j to end at i - which would give a value of dp_j + 1.
    So, we have dp_i = 1 + \max(dp_j), taken across all j \lt i such that A_j = A_i - 1.

Now, the first transition, with A_i = 1, is easy to maintain since we only need to store prefix maximums of the dp array.

The second one however is hard to do directly since there can be many valid indices j to iterate over.

To get around this, what we can do is store the DP by value instead of index.

That is, we redefine the state as follows: dp_x is the maximum possible answer so far, such that the last subarray ends with x.
Then,

  • If A_i = 1, we have dp_1 = 1 + \max(dp_0, dp_1, dp_2, \ldots, dp_N) since we can take any previous ending value and be fine.
  • If A_i \ge 1, we have dp_x = \max(dp_x, 1 + dp_{x-1}) where x = A_i.
    This is because we must choose some previous subarray ending with the value x-1 and extend it to x.

Now the second transition is trivial, and to do the first one quickly we only need to maintain the global maximum of the DP array as a separate variable.

The base states are dp_0 = 0 and dp_x = -\infty for all x \gt 0, to signify that we don’t yet have any subarrays ending with x.
The final answer is simply the maximum element of the DP array, after processing all N elements.

This gives us a simple linear-time solution to the problem.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    dp = [-10**9]*(n+1)
    dp[0] = 0
    mx = 0
    for x in a:
        if x == 1:
            dp[1] = max(dp[1], 1 + mx)
            mx = max(mx, dp[1])
        else:
            dp[x] = max(dp[x], 1 + dp[x-1])
            mx = max(mx, dp[x])
    print(max(dp))