コンテンツにスキップ

DOJ Beginner Contest 11 C - Farewell

サイト
DOJ
コンテスト
DOJ Beginner Contest 11
問題
C - Farewell

整数列 A1,A2,…,ANA_1, A_2, \dots, A_N があります。要素を 1 つ選んで削除すると、その左にあった要素はすべて 11 増え、右にあった要素はすべて 11 減ります。

要素が 1 つになるまで削除を繰り返したとき、最後に残る値の最大値を求める問題です。値は負になってもかまいません。

最後に残す要素を AiA_i と決めます(1-indexed)。

AiA_i より左の要素を削除すると、AiA_i は削除した要素の右にあるので 11 減ります。AiA_i より右の要素を削除すると 11 増えます。左には i−1i - 1 個、右には N−iN - i 個の要素があり、どれもいつかは削除されるので、削除の順番によらず最後の値は

Ai−(i−1)+(N−i)A_i - (i - 1) + (N - i)

です。これを ii について最大化すれば答えです。O(N)O(N) で求まります。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
ans = -float("inf")
for i in range(N):
ans = max(ans, A[i] - i + N - i - 1)
print(ans)

コードでは 0-indexed なので、左に ii 個、右に N−i−1N - i - 1 個の要素があります。