DOJ Beginner Contest 11 C - Farewell
- サイト
- DOJ
- コンテスト
- DOJ Beginner Contest 11
- 問題
- C - Farewell
整数列 があります。要素を 1 つ選んで削除すると、その左にあった要素はすべて 増え、右にあった要素はすべて 減ります。
要素が 1 つになるまで削除を繰り返したとき、最後に残る値の最大値を求める問題です。値は負になってもかまいません。
最後に残す要素を と決めます(1-indexed)。
より左の要素を削除すると、 は削除した要素の右にあるので 減ります。 より右の要素を削除すると 増えます。左には 個、右には 個の要素があり、どれもいつかは削除されるので、削除の順番によらず最後の値は
です。これを について最大化すれば答えです。 で求まります。
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 なので、左に 個、右に 個の要素があります。