概要

与えられた \(N\) 個の整数からなる数列の中で、連続する部分列の合計値の最大を求める問題です。ただし、空の部分列（要素を1つも選ばない）を選択することも可能であり、その場合の合計値は \(0\) となります。

考察

素朴なアプローチ

すべての連続部分列の組み合わせを試す方法が考えられます。 部分列の開始位置を \(l\)、終了位置を \(r\) とすると、その組み合わせは \(O(N^2)\) 通り存在します。それぞれの和を計算するのに \(O(N)\) かかると全体で \(O(N^3)\)、累積和を使っても \(O(N^2)\) の計算量となります。 今回の制約は \(N \leq 2 \times 10^5\) であるため、\(O(N^2)\) では実行時間制限（通常2秒程度）に間に合いません。そのため、より効率的な \(O(N)\) のアルゴリズムが必要です。

効率的な解法へのヒント

数列を左から順に見ていき、「現在の要素を含めた連続部分列の和」がどう変化するかを考えます。 ある位置までの合計が負になってしまった場合、その負の値を引き継いで次の要素を足すよりも、そこで一旦区切り、次の要素から新しく合計を計算し直す（あるいは空の状態に戻す）方が、それ以降の合計値を大きくできる可能性が高まります。

これは「カデーンのアルゴリズム (Kadane’s Algorithm)」と呼ばれる有名な手法の考え方です。

アルゴリズム

カデーンのアルゴリズム

以下の手順で、数列を1回走査するだけで最大和を求めることができます。

1. これまでの最大合計値を保持する変数 ans を \(0\) で初期化します（空の部分列を考慮）。
2. 現在注目している連続部分列の合計を保持する変数 current_sum を \(0\) で初期化します。
3. 数列の各要素 \(A_i\) について、以下の操作を繰り返します。
   • current_sum に \(A_i\) を加算する。
   • もし current_sum が負になったら、current_sum を \(0\) にリセットする。
     • これは「負の合計を引き継ぐくらいなら、ここで区切って空の状態から再スタートしたほうが得である」という判断に相当します。
   • ans を max(ans, current_sum) で更新する。

この方法により、すべての要素を1度ずつ確認するだけで、どこから始めてどこで終わるのが最適かを効率的に判定できます。

計算量

• 時間計算量: \(O(N)\)
  • 数列の要素を一度ずつ走査するため、要素数 \(N\) に比例した時間で計算が完了します。
• 空間計算量: \(O(N)\)
  • 入力値をリストとして保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) が \(2 \times 10^5\) と大きいため、Pythonでは sys.stdin.read().split() を使用して一括で入力を読み込むことで、実行時間を短縮しています。

• 初期値の設定: 問題文に「要素を1つも選ばないことも許されており、その場合の合計は0とする」とあるため、ans の初期値を \(0\) にしておくことで、すべての要素が負の場合でも正しく \(0\) を出力できます。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにします。
    # この方法は、競技プログラミングにおいてPythonで大量の入力を高速に処理する一般的な手法です。
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は終了します。
    if not input_data:
        return
    
    # 最初の要素は数列の長さ N です。
    n = int(input_data[0])
    
    # カデーンのアルゴリズム（Kadane's Algorithm）を用いて、連続部分列の最大和を求めます。
    # 問題文より、空の部分列（和が0）も許容されるため、ans の初期値は 0 とします。
    ans = 0
    current_sum = 0
    
    # 数列の各要素 A_i についてループを回します。
    # インデックス 1 から n までの要素が数列のデータです。
    for i in range(1, n + 1):
        # 現在の値を整数に変換します。
        val = int(input_data[i])
        
        # 現在の連続部分列の合計に val を加算します。
        current_sum += val
        
        # もし合計が負になった場合、それまでの部分列を破棄し、
        # 合計を 0 にリセットします（これは空の部分列を選ぶ、あるいは次の要素から新しく始めることに相当します）。
        if current_sum < 0:
            current_sum = 0
        # これまでの最大合計値（ans）よりも現在の合計（current_sum）が大きい場合、更新します。
        elif current_sum > ans:
            ans = current_sum
            
    # 選考対象（合計が0以上）となる連続部分列の中での最大値を出力します。
    print(ans)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。