JUMPCOST - 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:

None

PROBLEM:

You’re given an array A.
You start at position 1.
From i, you can move to j if i \lt j, adding A_j - j + i to your score.
Find the maximum possible final score.

EXPLANATION:

Suppose the sequence of indices we jump to is i_1, i_2, \ldots, i_K.
Then the final score is

(A_{i_1} - i_1 + 1) + (A_{i_2} - i_2 + i_1) + \ldots + (A_{i_K} - i_K + i_{K-1})

Observe that the indices alternately add and subtract, and so mostly end up cancelling each other out.
In particular the above expression reduces to just

(A_{i_1} + A_{i_2} + \ldots + A_{i_K}) - i_K + 1

Now, suppose we decide on index i to be the last index.
From the index part of the expression, there’s a constant cost of -i + 1.
We’re also forced to add A_{i} itself.

However, 2, \ldots, i-1 can be freely chosen or not by us, to visit along the way.
For each chosen index, we only add the value at this index to the score.

So, clearly it’s optimal to only pick those indices with positive values at them.

Thus, if i is fixed, the optimal score with this as the final index equals

A_i - i + 1 + \sum_{j=2}^{i-1} \max(0, A_j)

This gives an easy algorithm in \mathcal{O}(N^2) time by just computing this for all i in linear time each and taking the best answer.

It’s possible to improve this to linear time by simply storing the prefix sums of \max(0, A_j) instead of recomputing each time.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = [0] + list(map(int, input().split()))
    
    ans = 0
    sm = 0
    for i in range(2, n+1):
        ans = max(ans, a[i] - i + 1 + sm)
        sm += max(a[i], 0)
    print(ans)