概要

連続部分列（区間）の和の最大値を求める問題です。ただし和が負になる区間は選ばず、空区間（和 \(0\)）も許されます。

考察

連続区間の和を最大化したいとき、素朴にすべての区間 \((l, r)\) を試すと区間数は \(O(N^2)\) 個あります。\(N \le 2 \times 10^5\) なので、これは確実に時間切れになります。

ここで重要な観察は次の通りです：

• ある位置まで見たとき、「その位置で終わる連続部分列の最大和」だけ分かれば、次の要素を処理できます。
• さらに本問では「和が負の区間は選ばない」「空区間OK（和0）」なので、途中で部分和が負になったら その区間は捨てて 0 からやり直す のが最適です。
  なぜなら、負の和を抱えたまま次に進むと、その後にどんな正の値が来ても合計を減らしてしまうからです。

具体例：\(A = [3, -5, 4, 2]\) - 最初の \(3\) は良い（和 \(3\)） - 次に \(-5\) を足すと \(3 + (-5) = -2\) で負になる
→ この区間は捨てて、次は「空区間（0）」から再スタート - その後 \(4, 2\) を足して \(6\) が最大

この「負になったらリセットする」考え方で、1回の走査で最大値を求められます。

アルゴリズム

これは Kadane 法（最大部分和の線形時間アルゴリズム） の「空区間OK版」です。

• cur：現在位置で終わる、和が \(0\) 以上であるような連続部分列の最大和
• best：これまで見た中での最大値

各要素 \(x\) について次を行います：

1. cur = max(0, cur + x)
   
   • 直前までの良い区間に \(x\) を足す（cur + x）
   • もし負になったら、その区間は採用せず空区間に戻す（0）
2. best = max(best, cur) で最大値を更新

初期値を cur = 0, best = 0 にすることで、全要素が負でも答えは空区間の \(0\) になります（問題条件に一致）。

計算量

• 時間計算量: \(O(N)\)（配列を1回なめるだけ）
• 空間計算量: \(O(1)\)（追加の配列を使わない）

実装のポイント

• cur = max(0, cur + x) の「0で打ち切る」が本問の肝です（空区間を許すため）。

• \(A_i\) は最大で \(10^9\)、\(N\) も大きいので合計は大きくなりますが、Python の int は任意精度なのでオーバーフローを気にしなくてよいです。

• 入力が大きいので sys.stdin.buffer.read() による高速入力にしています。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    a = data[1:1+n]

    best = 0
    cur = 0
    for x in a:
        cur = max(0, cur + x)
        if cur > best:
            best = cur

    print(best)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。