概要

\(N\) 日間の損益データが順に与えられ、各 \(k = 1, 2, \ldots, N\) について「最初の \(k\) 日間における連続部分配列の最大和」を求める問題です。これは Kadane のアルゴリズムを逐次的に適用することで効率的に解けます。

考察

素朴なアプローチとその問題点

各 \(k\) について、すべての区間 \([l, r]\)（\(1 \leq l \leq r \leq k\)）を試して合計を求めると、1つの \(k\) に対して \(O(k^2)\)、全体では \(O(N^3)\) かかります。累積和を使っても \(O(N^2)\) で、\(N \leq 2 \times 10^5\) では間に合いません（TLE）。

重要な気づき

「連続部分配列の最大和」は Kadane のアルゴリズム で \(O(N)\) で求められる有名な問題です。さらに、この問題では \(k = 1, 2, \ldots, N\) と順に答えを出力する必要がありますが、Kadane のアルゴリズムはもともと配列を左から1要素ずつ処理するため、途中経過をそのまま各 \(k\) の答えとして出力できます。

Kadane のアルゴリズムの考え方

次の2つの値を管理します：

• \(\text{max\_ending\_here}\)：現在の位置 \(k\) で終わる連続部分配列の最大和
• \(\text{max\_so\_far}\)：これまでに見た連続部分配列の最大和（全体の答え）

\(k\) 番目の要素 \(B_k\) を見たとき、\(k\) で終わる最大部分配列は次の2択です：

1. 直前までの部分配列を延長する：\(\text{max\_ending\_here} + B_k\)
2. \(B_k\) から新しく始める：\(B_k\)

つまり \(\text{max\_ending\_here} = \max(\text{max\_ending\_here} + B_k,\ B_k)\) と更新します。

具体例：\(B = [3, -5, 4, 2, -1]\) の場合

\(k\)	\(B_k\)	\(\text{max\_ending\_here}\)	\(\text{max\_so\_far}\)
1	3	\(3\)	\(3\)
2	-5	\(\max(3 + (-5),\ -5) = -2\)	\(\max(3, -2) = 3\)
3	4	\(\max(-2 + 4,\ 4) = 4\)	\(\max(3, 4) = 4\)
4	2	\(\max(4 + 2,\ 2) = 6\)	\(\max(4, 6) = 6\)
5	-1	\(\max(6 + (-1),\ -1) = 5\)	\(\max(6, 5) = 6\)

出力は \(3, 3, 4, 6, 6\) です。

アルゴリズム

1. \(\text{max\_ending\_here} = B_1\)、\(\text{max\_so\_far} = B_1\) で初期化し、\(k=1\) の答えを出力。
2. \(k = 2, 3, \ldots, N\) について：
   • \(\text{max\_ending\_here} = \max(\text{max\_ending\_here} + B_k,\ B_k)\)
   • \(\text{max\_so\_far} = \max(\text{max\_so\_far},\ \text{max\_ending\_here})\)
   • \(\text{max\_so\_far}\) を \(k\) 行目の答えとして出力。

計算量

• 時間計算量: \(O(N)\) — 配列を1回走査するだけ
• 空間計算量: \(O(N)\) — 入力配列と出力配列の格納（変数のみなら \(O(1)\) で済む）

実装のポイント

• 空区間は選べないため、すべて負の値でも最大の1要素を選ぶ必要があります。Kadane のアルゴリズムでは \(\text{max\_ending\_here}\) が必ず1要素以上を含むので、この条件は自然に満たされます。

• 出力が \(N\) 行と多いため、print を毎回呼ぶと遅くなります。リストに溜めて最後に sys.stdout.write でまとめて出力するのが高速化のポイントです。

• \(B_i\) の値が \(\pm 10^9\) で \(N\) が最大 \(2 \times 10^5\) なので、合計値は最大 \(2 \times 10^{14}\) 程度になり得ます。Python では整数のオーバーフローはありませんが、C++ などでは long long が必要です。

  ソースコード

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    B = list(map(int, input().split()))
    
    # For each k, we need the maximum subarray sum of B[0..k-1]
    # This is the classic Kadane's algorithm, but we need to output for each prefix.
    # 
    # We maintain:
    # - max_ending_here: maximum sum of subarray ending at current position (must include current element)
    # - max_so_far: overall maximum subarray sum seen so far
    
    out = []
    max_ending_here = B[0]
    max_so_far = B[0]
    out.append(max_so_far)
    
    for k in range(1, N):
        # Kadane's: extend previous subarray or start new one at k
        if max_ending_here + B[k] > B[k]:
            max_ending_here = max_ending_here + B[k]
        else:
            max_ending_here = B[k]
        
        if max_ending_here > max_so_far:
            max_so_far = max_ending_here
        
        out.append(max_so_far)
    
    sys.stdout.write('\n'.join(map(str, out)) + '\n')

main()

---

この解説は claude4.6opus-thinking によって生成されました。