公式

B - 損益の最大区間和 / Maximum Subarray Sum of Profit and Loss 解説 by admin

GPT 5.2 High

概要

各 \(k=1..N\) について、\(1\) 日目から \(k\) 日目までの中で「連続する区間(長さ \(\ge 1\))」の損益合計の最大値(最大部分和)を求めます。

考察

求めたいのは、配列 \(B_1..B_k\) に対する最大部分配列和です。これを各 \(k\) ごとに独立に計算すると、

  • すべての区間 \((l,r)\) を試すと \(O(k^2)\)
  • それを \(k=1..N\) で繰り返すと合計 \(O(N^3)\)(または工夫しても \(O(N^2)\) 程度)

となり、\(N \le 2\times 10^5\) では間に合いません(TLE)。

ここで重要な観察は次の2点です。

  1. 「\(k\) までの答え」は「\(k-1\) までの答え」から更新できる
  2. \(k\) で終わる最大区間和(末尾固定)さえ分かれば、全体の最大も更新できる

具体的に、\(k\) 日目の値を \(x=B_k\) とすると、\(k\) 日目で終わる最大区間和は - \(k\) 日目だけの区間:和は \(x\) - 以前の「\(k-1\) 日目で終わる最大区間和」に \(x\) を足して伸ばす:和は \(\text{cur}+x\)

のどちらか大きい方です。もしこれまでの区間和が負なら、伸ばすより新しく始めた方が有利になります。

また、\(1..k\) の中での最大区間和(答え)は、 - すでに \(1..k-1\) で達成している最大値 - \(k\) で終わる最大区間和

の最大です。

例えば \(B=[-2, 3, -1, 4]\) のとき: - \(k=1\): 最大は \(-2\) - \(k=2\): \(3\) 単体が良いので最大は \(3\) - \(k=3\): \(3+(-1)=2\) が \(-1\) より良い、最大は \(3\) のまま - \(k=4\): \(2+4=6\) が良い、最大は \(6\)

この更新を1回ずつ行えば、全ての \(k\) の答えを高速に出せます。

アルゴリズム

Kadane のアルゴリズム(最大部分配列和)を「各接頭辞 \(1..k\) についての答え」を出す形にします。

  • \(\text{cur}\):現在の位置 \(i\) で終わる最大区間和
    $\( \text{cur} = \max(B_i,\ \text{cur}+B_i) \)$
  • \(\text{best}\):これまで(\(1..i\))の最大区間和
    $\( \text{best} = \max(\text{best},\ \text{cur}) \)$

各 \(i=1..N\) で \(\text{best}\) を出力すれば、それが \(k=i\) の答えです。

ポイント:空区間は選べないので、初期値は \(0\) ではなく \(B_1\) で初期化します(全て負の場合でも正しく負の最大値を返すため)。

計算量

  • 時間計算量: \(O(N)\)(各要素を1回ずつ処理)
  • 空間計算量: \(O(1)\)(出力用を除けば定数、実装では出力を貯めて \(O(N)\))

実装のポイント

  • 初期化を cur = best = B[0] とする(空区間禁止への対応)

  • 更新式は cur = max(x, cur + x)(「伸ばす」か「新規開始」か)

  • 各 \(k\) の答えは best をそのまま出力すればよい

  • 入力が大きいので sys.stdin.buffer.read() を使って高速化する

    ソースコード

import sys

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

    res = []
    cur = b[0]
    best = b[0]
    res.append(str(best))

    for i in range(1, n):
        x = b[i]
        cur = max(x, cur + x)
        if cur > best:
            best = cur
        res.append(str(best))

    sys.stdout.write("\n".join(res))

if __name__ == "__main__":
    main()

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