B - 損益の最大区間和 / Maximum Subarray Sum of Profit and Loss 解説
by
MMNMM
\(B _ i\) の累積和 \(\displaystyle S _ i\coloneqq B _ 1+B _ 2+\cdots+B _ {i-1}\) を使うと、求める値 \(\displaystyle\max _ {1\le l\le r\le k}\sum _ {i=l} ^ rB _ i\) は \(\displaystyle\max _ {1\le l\le r\le k}\bigl(S _ {r+1}-S _ l\bigr)\) と書くことができます。 これは、さらに \[\begin{aligned}\max _ {1\le l\le r\le k}\bigl(S _ {r+1}-S _ l\bigr)&=\max _ {1\le r\le k}\Bigl(\max _ {1\le l\le r}\bigl(S _ {r+1}-S _ l\bigr)\Bigr)\\&=\max _ {1\le r\le k}\Bigl(S _ {r+1}+\max _ {1\le l\le r}(-S _ l)\Bigr)\\&=\max _ {1\le r\le k}\Bigl(S _ {r+1}-\min _ {1\le l\le r}(S _ l)\Bigr)\end{aligned}\] と変形することができます。
よって、\(S _ i\) の先頭からの累積 \(\min\) として \(\displaystyle M _ i\coloneqq\min\lbrace S _ 1,S _ 2,\ldots,S _ i\rbrace\) を使うことで、求める値を \(\displaystyle\max _ {1\le r\le k}\bigl(S _ {r+1}-M _ r\bigr)\) とすることができます。 これは \(S _ {r+1}-M _ r\) の先頭からの累積 \(\max\) なので、先頭から順に \(S _ i,M _ i\) などを管理しながら答えを求めることができます。
時間計算量は \(O(N)\) となり、十分高速です。
実装例は以下のようになります。
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int N;
cin >> N;
long prefix_sum = 0, prefix_sum_min = 0, ans = -1000000000;
for (int i = 0; i < N; ++i) {
int B;
cin >> B;
prefix_sum += B; // 累積和に B を足して
ans = max(ans, prefix_sum - prefix_sum_min); // r = i のときの最大値とこれまでの値の max をとる
prefix_sum_min = min(prefix_sum_min, prefix_sum); // 累積和の prefix min を更新
cout << ans << endl; // 答えを出力
}
return 0;
}
N = int(input())
prefix_sum = 0
prefix_sum_min = 0
ans = -1000000000
for b in map(int, input().split()):
prefix_sum += b # 累積和に b を足して
ans = max(ans, prefix_sum - prefix_sum_min) # r = i のときの最大値とこれまでの値の max をとる
prefix_sum_min = min(prefix_sum_min, prefix_sum) # 累積和の prefix min を更新
print(ans) # 答えを出力
