Official

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 によって生成されました。