B - 損益の最大区間和 / Maximum Subarray Sum of Profit and Loss 解説 by admin
Gemini 3.1 Pro (Thinking)概要
与えられた数列の先頭から \(k\) 番目までのデータにおいて、連続する部分列の和の最大値(最大区間和)を各 \(k = 1, 2, \ldots, N\) について求める問題です。
考察
この問題は、有名な「最大部分配列和問題(Maximum Subarray Sum)」の途中の状態をすべて出力する問題と言えます。
まず、素朴な方法を考えてみましょう。各 \(k\) について、すべての区間 \((l, r)\) の和を計算して最大値を求めようとすると、累積和を使ったとしても \(O(k^2)\) の時間がかかります。これを \(k = 1\) から \(N\) まで繰り返すと全体の計算量は \(O(N^3)\) になってしまいます。制約の \(N = 2 \times 10^5\) では、到底実行時間制限(TLE)に間に合いません。
そこで、計算を効率化するための重要な気づきとして、「\(i\) 日目で終わる区間の最大和」に注目します。 \(i\) 日目で終わる区間の和を最大化したい場合、選択肢は以下の2つしかありません。 1. \(i-1\) 日目で終わる区間に、\(i\) 日目の損益 \(B_i\) を連結する。 2. 過去の区間を捨てて、\(i\) 日目単独で新しい区間を開始する。
どちらを選ぶべきかは、\(i-1\) 日目で終わる区間の最大和が「正の数」か「0以下の数」かで決まります。 - もし過去の和が正(\(>0\))なら、それに \(B_i\) を足した方が和は大きくなります。 - もし過去の和が赤字(\(\le 0\))なら、これまでの区間を引き継ぐと損をしてしまうため、\(B_i\) 単独で再スタートした方が和は大きくなります。
このようにして求めた「各日で終わる区間の最大和」のうち、これまでの過去の最大値を保持し続ければ、それが各 \(k\) における答えになります。
アルゴリズム
この解法はKadaneのアルゴリズム(カダーンのアルゴリズム)を応用したものです。
- 変数を2つ用意し、どちらも最初の要素 \(B_1\) で初期化します。
current_max: 直近の \(i\) 日目を必ず終端とする区間の最大和global_max: \(1\) 日目から \(i\) 日目までの中で、すべての区間における最大和
- \(k=1\) の答えとして
global_maxを記録します。 - \(i = 2, 3, \ldots, N\) の順に以下の更新を行います。
current_maxが正であれば、current_maxに \(B_i\) を足します。current_maxが0以下であれば、current_maxを \(B_i\) で上書きします(再スタート)。- もし
current_maxがglobal_maxを上回っていれば、global_maxを更新します。 - その時点の
global_maxを \(k=i\) の答えとして記録します。
- 記録した答えを順番に出力します。
具体例:\(B = [3, -5, 4, -1, 3]\) の場合
- \(i=1\) (\(B_1=3\)): current_max = \(3\), global_max = \(3\)(出力: \(3\))
- \(i=2\) (\(B_2=-5\)): 前回の current_max (\(3\)) \(> 0\) なので足す。current_max = \(3 + (-5) = -2\)。global_max は \(3\) のまま(出力: \(3\))
- \(i=3\) (\(B_3=4\)): 前回の current_max (\(-2\)) \(\le 0\) なので再スタート。current_max = \(4\)。global_max は \(4\) に更新される(出力: \(4\))
- \(i=4\) (\(B_4=-1\)): 前回の current_max (\(4\)) \(> 0\) なので足す。current_max = \(4 + (-1) = 3\)。global_max は \(4\) のまま(出力: \(4\))
- \(i=5\) (\(B_5=3\)): 前回の current_max (\(3\)) \(> 0\) なので足す。current_max = \(3 + 3 = 6\)。global_max は \(6\) に更新される(出力: \(6\))
計算量
- 時間計算量: \(O(N)\)
- 配列を先頭から1回ループして足し算や比較を行うだけなので、要素数 \(N\) に比例した時間で処理が完了します。
- 空間計算量: \(O(N)\)
- 入力データの保持や、出力用の配列を保持するために \(O(N)\) のメモリを使用します。アルゴリズム自体に必要な追加変数は数個のため、空間効率も非常に優れています。
実装のポイント
空の区間は選べないという条件: すべての日が赤字(負の数)の場合でも、どれか1日は選ばなければなりません。そのため、
current_maxやglobal_maxの初期値を \(0\) にするのではなく、必ず \(1\) 日目の値 \(B_1\) で初期化するようにしてください。高速な入出力: \(N\) が最大 \(2 \times 10^5\) と大きいため、Pythonの場合は
printを毎回呼ぶよりも、答えをリスト(配列)に文字列として溜めておき、最後に'\n'.join(out)でまとめて出力すると実行時間を短縮できます。ソースコード
import sys
def main():
input_data = sys.stdin.read().split()
if not input_data:
return
N = int(input_data[0])
B = [int(x) for x in input_data[1:N+1]]
current_max = B[0]
global_max = B[0]
out = [str(global_max)]
for i in range(1, N):
val = B[i]
if current_max > 0:
current_max += val
else:
current_max = val
if current_max > global_max:
global_max = current_max
out.append(str(global_max))
print('\n'.join(out))
if __name__ == '__main__':
main()
この解説は gemini-3.1-pro-thinking によって生成されました。