B - 損益の最大区間和 / Maximum Subarray Sum of Profit and Loss Editorial by admin
DeepSeek V3概要
各 \(k\) に対して、最初の \(k\) 日間の連続する区間の最大和を求める問題です。Kadaneのアルゴリズムを活用して効率的に解きます。
考察
素朴なアプローチでは、各 \(k\) に対して全ての連続区間の和を計算すると \(O(N^3)\) の時間がかかり、制約 \(N \leq 2 \times 10^5\) では到底間に合いません。
重要な観察は、\(k\) 日目までの最大区間和は、以下の2つの値のいずれかになることです: 1. \(k\) 日目のみを含む区間(値: \(B_k\)) 2. \(k-1\) 日目までの最大区間和を伸ばした区間(値: \(dp[k-1] + B_k\))
ここで \(dp[i]\) は \(i\) 日目で終わる連続区間の最大和を表します。さらに、全体の最大値は各ステップで \(dp[i]\) とこれまでの最大値 \(ans[i-1]\) を比較して更新できます。
アルゴリズム
Kadaneのアルゴリズムを応用します: 1. \(dp[0] = B[0]\) で初期化(最初の日のみ) 2. \(ans[0] = B[0]\) で初期化 3. \(i = 1\) から \(N-1\) まで以下を繰り返す: - \(dp[i] = \max(B[i], dp[i-1] + B[i])\) (現在の日のみ vs 前の区間を延伸) - \(ans[i] = \max(ans[i-1], dp[i])\) (これまでの最大値 vs 新しい区間和) 4. \(ans\) 配列を順に出力
この方法で、各 \(k\) に対する最大区間和を効率的に求められます。
計算量
- 時間計算量: \(O(N)\)
- 配列を1回走査するだけ
- 空間計算量: \(O(N)\)
- \(dp\) 配列と \(ans\) 配列を使用
実装のポイント
初期化では最初の要素を正しく設定
負の値も扱えるように、区間は必ず1日以上含む
配列のインデックスに注意(0-indexed)
大きな数値に対応するため、整数型を使用
ソースコード
import sys
def main():
data = sys.stdin.read().split()
n = int(data[0])
B = list(map(int, data[1:1+n]))
dp = [0] * n
ans = [0] * n
dp[0] = B[0]
ans[0] = B[0]
for i in range(1, n):
dp[i] = max(B[i], dp[i-1] + B[i])
ans[i] = max(ans[i-1], dp[i])
for a in ans:
print(a)
if __name__ == "__main__":
main()
この解説は deepseekv3 によって生成されました。