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点です。
- 「\(k\) までの答え」は「\(k-1\) までの答え」から更新できる
- \(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 によって生成されました。