MAXSUM77 - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given an array A.
You can remove either its first or its last element. This must be done K times.
Find the maximum possible sum of the remaining elements.

EXPLANATION:

Suppose we delete from the front x times and from the back y times.
Then, we must have x+y = K.
Thus, y = K-x

If we do this, the elements remaining in the array will hence be exactly

[A_{x+1}, A_{x+2}, \ldots, A_{N-y}] = [A_{x+1}, A_{x+2}, \ldots, A_{N-K+x}]

Note that this depends only on x.

So, we can simply try all 0 \le x \le K, compute the sum of the corresponding elements, and then take the largest such sum.

If implemented directly this has a runtime of \mathcal{O}(N^2), which is good enough for the constraints.
It’s possible to optimize this to \mathcal{O}(N) time in a variety of ways (prefix sums, sliding window are two of them.)

TIME COMPLEXITY:

\mathcal{O}(N^2) or \mathcal{O}(N) per testcase.

CODE:

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