概要

与えられた日次損益データについて、各時点での連続区間和の最大値を順番に求める問題です。

考察

この問題は、いわゆる「部分配列の最大和（Maximum Subarray Problem）」をオンラインクエリに対応させたものです。愚直な方法では、各 \(k\) に対してすべての区間 \([l, r]\) を試すことで答えを求められますが、これは \(O(N^3)\) となり、\(N\) が最大 \(2 \times 10^5\) なので現実的ではありません。

さらに、各 \(k\) ごとに独立に最大区間和を求めるのではなく、前の結果を利用して効率的に更新できることに気づくことが重要です。つまり、ある日までに得られている最適な区間の情報を活用して、次の日に最適解を更新していくことができます。

このような考えに基づいて、動的計画法的なアプローチが有効になります。特に有名なのは Kadane’s Algorithm と呼ばれる手法で、線形時間で最大部分和を求めることができます。

アルゴリズム

この問題では、各 \(k = 1, 2, ..., N\) について、配列の先頭から \(k\) 番目までの要素のみを考えたときの連続部分列の和の最大値を求める必要があります。

そこで、以下のような変数を管理します：

• max_ending_here: 現在位置を必ず含むような連続部分列の和の最大値
  
• max_so_far: これまで見てきた範囲での全体の最大値
  

アルゴリズムの流れは以下の通りです：

1. 最初の要素 \(B_0\) については、選べる区間がそれだけなので、初期値として設定します：
   • max_ending_here = B[0]
   • max_so_far = B[0]
2. 各 \(i = 1, 2, ..., N-1\) に対して以下を行う：
   • 新しい要素 \(B[i]\) を加えたときに、今までの続きにするか新しい区間を始めるか選択します：
     • max_ending_here = max(B[i], max_ending_here + B[i])
   • 全体の最大値を更新します：
     • max_so_far = max(max_so_far, max_ending_here)
3. 各ステップで求めた max_so_far を出力すれば完了です。

このようにすることで、各ステップで最大部分和を \(O(1)\) で更新でき、全体で \(O(N)\) で解くことができます。

具体例

例えば入力が [1, -3, 2, 1, -1] の場合、

k	B[k]	max_ending_here	max_so_far
1	1	1	1
2	-3	-2	1
3	2	2	2
4	1	3	3
5	-1	2	3

したがって出力は：

1
1
2
3
3

となります。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\) （入力を除く）

実装のポイント

• 各日について「そこまでの最適解」を再利用するのがポイント

• max_ending_here は現在地を必ず含む区間の最大和であり、毎回更新される

• max_so_far は全体を通して見た最大値であり、常に記録しておく必要がある

• 最初の1つ目の日については例外処理として最初に処理しておくと、ループ内で統一的に扱えて便利

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    B = list(map(int, data[1:]))

    max_ending_here = B[0]
    max_so_far = B[0]
    print(max_so_far)

    for i in range(1, N):
        max_ending_here = max(B[i], max_ending_here + B[i])
        max_so_far = max(max_so_far, max_ending_here)
        print(max_so_far)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。