問題
円環状に並んだ $N$ 個の整数 $a_1,\dots,a_N$（$a_N$の次は$a_1$）が与えられる。連続する部分列（円環をまたいでもよい）の和の最大値を求めよ。ただし空の部分列は選べない。
制約
| パラメータ | 範囲 | 備考 |
|---|---|---|
| $N$ | $1 \le N \le 2\times10^5$ | 要素数 |
| $a_i$ | $-10^9 \le a_i \le 10^9$ | 負も許容 |
入出力例
入力例1
5
1 -2 3 -2 5出力例1
7円環をまたぐ選び方 $3,-2,5,1$（インデックス3,4,5,1）の和が7で最大。
入力例2
3
-3 -1 -2出力例2
-1全要素が負のときは円環を跨ぐ候補が無効になるため、通常の最大部分和（最大要素1つ）を採用。
概念図
ヒント
ヒント1（方向性）
円環を跨がない最大部分和はKadaneで$O(N)$求まる。円環を跨ぐ場合は「使わない連続部分」を最小にする、と考えを反転できないか。
ヒント2（アプローチ）
円環を跨ぐ最大部分和 = 全体の総和 − （跨がない）最小部分和。ただし最小部分和が全体と一致すると空集合相当になるため除外が必要。
ヒント3（ほぼ答え）
total = sum(a)
max_sum = kadane_max(a)
min_sum = kadane_min(a)
if max_sum < 0:
answer = max_sum # 全要素が負 → 円環候補は無効
else:
answer = max(max_sum, total - min_sum)模範解答
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:1 + n]))
total = sum(a)
cur_max = a[0]
max_sum = a[0]
for x in a[1:]:
cur_max = max(x, cur_max + x)
max_sum = max(max_sum, cur_max)
cur_min = a[0]
min_sum = a[0]
for x in a[1:]:
cur_min = min(x, cur_min + x)
min_sum = min(min_sum, cur_min)
if max_sum < 0:
print(max_sum)
else:
print(max(max_sum, total - min_sum))
main()計算量: Kadaneを2回走らせるだけなので $O(N)$。
Step-by-Step 解説
Step 1: 通常の最大部分和をKadaneで求める
円環を跨がないケースの答え。「直前で終わる部分和の最大値」を保持する。
Step 2: 通常の最小部分和もKadaneで求める
最大化のロジックを反転させるだけで同様に求まる。
Step 3: 円環を跨ぐケースへの変換
円環を跨ぐ選択は「間の連続部分を選ばない」と等価。選ばない部分の和を最小化すれば跨ぐ側の和は最大化される。
Step 4: 全負ケースの例外処理
min_sumが全体と一致するとtotal-min_sum=0で空集合相当になるため、max_sum < 0のときはmax_sumを直接採用する。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 全負のとき0を答えにしてしまう | 空集合が選ばれるケースを見落とす | max_sum < 0のときmax_sumを採用 |
| 円環を跨ぐ際に要素を重複使用 | 分割条件の理解不足 | 「使わない部分」最小化の変換で自動排除 |
| Kadaneの初期値を0にする | 全負配列で過大評価 | 初期値はa[0]から開始 |
| maxのみでminを計算しない | 円環ケースの必要性を見落とす | maxとminの両方を計算 |
次のステップ
- 発展: 円環上で連続部分列を最大K個まで選べる場合（分割統治DP + Kadane拡張）
- 発展: 2次元円環（トーラス状グリッド）上の最大部分和への一般化
- 次回予告: Huffman符号化（貪欲法 + 優先度付きキュー）
自己評価
理解度: / /
自分の回答:
気づき・メモ: