最大部分配列問題

Blitz Round #25 B - Jump Trip Score

2026年10月4日

問題の概要

長さ $n$ の整数列 $a_1, \ldots, a_n$ があり、位置 $i = 1$ から出発して $i = n + 1$ に着いたら終わりです。スコアは $0$ から始まり、各位置で次のどちらかを行います。

$a_i$ をスコアに足して $i + 1$ に進む
正の整数 $d$ ( $i + d \le n + 1$ ) を選んで $i + d$ に跳ぶ(スコアは変わらない)

跳ぶ操作は高々 1 回まで使えるとき、最終スコアの最大値を求める問題です。

$1 \le n \le 4 \cdot 10^5$ 、 $-10^9 \le a_i \le 10^9$ 、テストケースの $n$ の総和は $4 \cdot 10^5$ 以下

正確な問題文は元の問題ページを見てください。

解法

$i$ から $i + d$ に跳ぶと、 $a_i, \ldots, a_{i+d-1}$ を飛ばすことになります。跳ぶのは高々 1 回なので、得られるスコアは

(\text{先頭からの連続部分の和}) + (\text{末尾までの連続部分の和})

で、間の 1 区間を飛ばした形になります(跳ばなければ全部の和)。

そこで

$L_k$ = 長さ $k$ 以下の接頭辞の和の最大値(空も含むので $0$ 以上)
$R_k$ = 位置 $k + 1$ 以降から始まる接尾辞の和の最大値(空も含む)

を累積和で求めておけば、答えは

\max_{0 \le k \le n} (L_k + R_k)

です。接頭辞と接尾辞が重ならないように、境目 $k$ を全通り試しています。計算量は $O(n)$ です。

解答コード

Python

for _ in range(int(input())):
    N = int(input())
    A = list(map(int,input().split()))
    dp0 = [0]
    x = 0
    for a in A:
        x += a
        dp0.append(max(x, dp0[-1]))
    dp1 = [0]
    x = 0
    for a in reversed(A):
        x += a
        dp1.append(max(x, dp1[-1]))
    dp1.reverse()
    print(max(x+y for x,y in zip(dp0,dp1)))

dp0 が $L$ 、dp1 が $R$ にあたります。