コンテンツにスキップ

最大部分配列問題

タグ「最大部分配列問題」の記事 3 件

最大部分配列問題のリンク集

最大部分配列問題について、参考になる記事や資料をまとめました。

最大部分配列問題は、数列の連続する部分列(部分配列)のうち、和が最大のものを求める問題です。全部の区間を調べると O(N2)O(N^2) ですが、Kadane のアルゴリズムを使うと O(N)O(N) で解けます。左から順に「その位置で終わる部分列の和の最大値」cc を c←max⁡(c+Ai,Ai)c \gets \max(c + A_i, A_i) で更新していき、cc が取った値の最大値が答えです。累積和 SS で見ると、右端 rr を決めたときの最大値は「SrS_r − それまでの SS の最小値」なので、累積和と累積 min でも O(N)O(N) で求まります。Kadane のアルゴリズムで持っている値は、この差にあたります。最小の和を求めたいときは、符号を反転させれば同じです。

空の部分列(和は 00)を許すかどうかで答えが変わるので、問題文をよく確認してください。許すなら答えは 00 以上で、許さないなら全要素が負のときの答えは最大の要素です。紹介する記事やコードでも扱いが分かれていて、初期値を 00 にするか A1A_1 にするかで違いが出ます。また、和は 64 bit 整数で持つ必要があることが多いです。

区間の最大部分配列和を、要素の更新をはさみながら何度も求めたいときは、セグメント木を使います。各ノードに「区間全体の和」「接頭辞の和の最大値」「接尾辞の和の最大値」「部分配列の和の最大値」の 4 つを持たせると、1 点の更新と区間のクエリがどちらも O(log⁡N)O(\log N) でできます。累積和そのものについては 累積和・いもす法のリンク集 も見てください。

  • Kadane’s Algorithm | 最大部分配列 問題(Ark’s Blog)
    • O(n3)O(n^3) と O(n2)O(n^2) の全探索、分割統治による O(nlog⁡n)O(n \log n)、Kadane のアルゴリズムによる O(n)O(n) を順に紹介しています。Kadane のアルゴリズムは、全探索の式の max⁡\max の順番を入れ替えて、右端 jj で終わる部分列の和の最大値 sjs_j の漸化式を導く形で説明しています。D 言語のコードつきで、空の部分列は許さない設定です。分割統治の節は概要だけです。
  • Kadane’s Algorithm - Maximum subarray problem(Janos、Zenn)
    • 全探索と Kadane のアルゴリズムを Python で比べています。先頭からの和が初めて負になる位置 kk より前から始まる部分列は考えなくてよい、という形で O(N)O(N) になる理由を説明しています(本人も厳密な証明ではないと書いています)。空の部分列は許さず、全要素が負なら最大の要素を返す実装です。
    • コードの List と inf は import されていないので、そのままでは動きません。
  • [競プロ][Max Subarray] Kadane’s Algorithm解説(awesam、Qiita)
    • DP[i]\mathrm{DP}[i] を「AiA_i で終わる部分配列の和の最大値」とする DP として説明し、答えは DP[n−1]\mathrm{DP}[n-1] ではなく DP\mathrm{DP} 全体の最大値であることを強調しています。LeetCode の Maximum Subarray を解く C++ のコードつきです。
    • コードは和を int で持っています。
  • Search the subarray with the maximum/minimum sum(cp-algorithms、英語)
    • 「Algorithm 1」で累積和から「それまでの最小の累積和」を引く方法を、「Algorithm 2」で Kadane のアルゴリズムを、それぞれ区間の位置も求めるコードつきで説明しています。後半では、長さに制約がある場合、2 次元版(下の節)、平均の最大値を二分探索で求める方法にも触れています。
    • コードは和を int で持っています。答えの初期値を a[0] にしているので空の部分列は許さない設定ですが、本文ではそのことに触れていません。また、Kadane のアルゴリズムを「1984 年に提案」としていますが、英語版 Wikipedia の歴史の節によると、考案されたのは 1977 年に問題が提案されてまもなくです。
  • More on Prefix Sums(USACO Guide、英語)
    • 最初の「Max Subarray Sum」の節で、固定した右端 rr について p[r]−min⁡l<rp[l]p[r] - \min_{l < r} p[l] を取る方法を説明し、C++・Java・Python のコードを載せています。下の CSES - Maximum Subarray Sum が例題です。別解として Kadane のアルゴリズムのコードも折りたたんで載っています。
    • 別解の Python のコードは数値を 1 行に 1 つずつ読んでいますが、CSES の入力は 1 行に並んでいるので、そのままでは動きません。
  • Maximum Subarray Sum using Divide and Conquer algorithm(GeeksforGeeks、英語)
    • 列を半分に分け、「左半分の答え」「右半分の答え」「中央をまたぐ部分列の最大値」の 3 つの最大値を取る O(nlog⁡n)O(n \log n) の方法を、C++・Java・Python などのコードで示しています。中央をまたぐ部分は、中央から左に伸ばした和の最大値と右に伸ばした和の最大値の和です。最後に Kadane のアルゴリズムのほうが良いと書いています。
    • コードは和を int で持っています。また、空間計算量を O(n)O(n) としていますが、追加で使うのは再帰の深さぶんの O(log⁡n)O(\log n) です。

左右の答えと「またぐ部分」を組み合わせるこの考え方を、区間ごとに前計算して持っておくのが次のセグメント木による方法です。

  • 最大部分配列問題(連続部分列の総和の最大値)をセグ木に載せる(hotman’s blog)
    • 「左端を含む最大値」「右端を含む最大値」「区間の最大値」「区間の総和」の 4 つ組がモノイドになり、2 つをつなげるときの式を分割統治と同じ考え方で導いています。短い記事で、単位元やコードは載っていません。
  • Finding subsegments with the maximal sum(cp-algorithms、英語)
    • セグメント木の記事の一節で、同じ 4 つの値を持たせる方法を、combine 関数と再帰のセグメント木の C++ のコードで説明しています。こちらは空の部分列を許す設定で、葉では和以外の値を max⁡(0,x)\max(0, x) にしています。
    • コードは値を int で持っています。

下の AtCoder Algorithm Lectures の講座は、空の部分列を許さない設定で同じモノイドを説明しています。設定によって単位元や葉の値が変わるので、見比べると違いがわかります。

長方形の領域の和の最大値を求める 2 次元版は、使う行の範囲(上端と下端)を全通り試し、各列の和を並べた 1 次元の列で最大部分配列問題を解くと、N×MN \times M のグリッドで O(N2M)O(N^2 M) です。

  • Two-dimensional case of the problem(cp-algorithms、英語)
    • 上の方法で O(n3)O(n^3) になることを説明しています。より速いアルゴリズムも知られているものの、複雑で実用的ではないことや、全点対最短路(min-plus の行列積)との関係にも触れています。
  • 区間クエリのためのモノイド設計
    • 「5.4 最大部分配列和」の節で、1 点更新と区間の最大部分配列和のクエリに答えるために、区間全体の和・接頭辞の和の最大値・接尾辞の和の最大値・答えの 4 つを持たせる設計を、結合の式と C++ のコードで説明しています。空でない部分列を対象にしていて、単位元は (−∞,−∞,−∞,0)(-\infty, -\infty, -\infty, 0) です。空の部分列を許す文献もあり、その場合は単位元が変わることにも触れています。
    • 「7.6 最大部分配列和(再考)」では、同じ問題を max-plus 半環上の 3×33 \times 3 行列の積として扱い、積の形が決まっているので 4 つの成分だけ持てばよいことを説明しています。「10.2」の関連問題には、下の CSES - Subarray Sum Queries が空の部分列の扱いの違いの注意つきで載っています。
    • −∞-\infty の具体的な値は書かれていません。−∞-\infty どうしを足すことがあるので、long long の最小値を使うとオーバーフローします。−1018-10^{18} 程度にしておくのが安全です。

主要な競プロライブラリ(ACL、Nyaan’s Library、Luzhiled’s Library など)には、最大部分配列問題そのものの実装はありません。セグメント木に載せるときは、上の講座の S、op、e をセグメント木のライブラリに渡します。

  • segtree のドキュメント(AtCoder Library)
    • ACL のセグメント木に渡す型 S・演算 op・単位元 e の決め方が書かれています。セグメント木のライブラリ全般は セグメント木のリンク集 を見てください。
  • Maximum Subarray Sum - Kadane’s Algorithm(GeeksforGeeks、英語)
    • O(n2)O(n^2) の全探索と Kadane のアルゴリズムを、C++・C・Java・Python・C#・JavaScript のコードで示しています。空でない部分列を対象にしていて、初期値を arr[0] にしています。
    • コードは和を int で持っています。C のコードは int を返す関数の結果を %lld で出力していて、書式が合っていません。

最大部分配列問題の記事は日本語版 Wikipedia にはありません。

  • Maximum subarray problem(英語版 Wikipedia)
    • 問題の定義と性質、歴史(Grenander が 2 次元版の簡略化として 1977 年に提案し、Shamos の O(nlog⁡n)O(n \log n) の分割統治を経て Kadane が O(n)O(n) の方法を考案したこと)、応用、Kadane のアルゴリズムを扱っています。Kadane のアルゴリズムは、空の部分列を許さない版と許す版の両方を Python のコードで示し、ループ不変条件で正しさを説明しています。2 次元版が O(n3)O(n^3) で解けることや、和の大きい順に kk 個の部分配列を求める一般化にも触れています。
    • 「Computing the best subarray’s position」の節は、区間の位置も求められると書いているだけで、コードはありません。
  • Donuts プロコンチャレンジ2014 C - ソーシャルゲーム:空でない連続部分列の和の最大値を求める基本形です。全要素が負のときは答えも負になります。
  • AtCoder Weekday Contest 0074 Beta B - 連続区間の最大和:空の区間を許す基本形で、答えは 00 以上です。和は 32 bit 整数に収まりません。
  • CSES - Maximum Subarray Sum:空でない部分配列の和の最大値を求めます。値が 10910^9 までなので、64 bit 整数が必要です。
  • CSES - Maximum Subarray Sum II:長さが aa 以上 bb 以下の部分配列に限ります。累積和の最小値を取る範囲が窓になるので、スライド最小値などで解けます。
  • ARC174 A - A Multiply:区間を CC 倍したときの総和の増分は (C−1)Ai(C - 1)A_i の区間和なので、この列の空を許す最大部分配列和を元の総和に足します。CC は負や 00 のこともあります。
  • ARC137 B - Count 1’s:00 を +1+1、11 を −1-1 に置き換えると、1 の個数の増分は区間和になり、取りうる値は空を許す最小部分配列和から最大部分配列和までの整数すべてです。
  • ABC466 E - Range Flip:操作する区間は交わらないとしてよく、Bi−AiB_i - A_i の列から高々 KK 個の交わらない区間を選んで和を最大化する問題になります。
  • AtCoder Weekday Contest 0097 Beta D - 最大長方形部分和:2 次元版です。空の領域は選べず、N,M≤500N, M \le 500 なので O(N2M)O(N^2 M) の方法が間に合います。
  • CSES - Subarray Sum Queries:1 点の更新のたびに、配列全体の最大部分配列和を答えます。空の部分配列を許します。
  • CSES - Subarray Sum Queries II:更新はなく、区間 [a,b][a, b] の中の最大部分配列和を答えるクエリを処理します。空の部分配列を許します。
  • Blitz Round #25 B - Jump Trip Score
    • 高々 1 回の跳躍で飛ばす区間を、接頭辞と接尾辞の和の最大値を累積和で求めて境目を全通り試す方法で解き、空を許す最小部分配列和を全体の和から引く見方も補足しています。
  • AALC001 I - Subarray
    • 互いに重ならない連続部分列を 2 個まで選ぶ版を、長さ 00 の部分列も許したうえで、選ぶ個数と区間の端に接するかどうかで分けた 8 つの値をセグメント木に載せて、1 点更新と区間クエリに答えています。

AALC001 I - Subarray

長さ NN の整数列 AA に対して、次の 2 種類のクエリを合計 QQ 個処理する問題です(1≤N,Q≤1051 \le N, Q \le 10^5, −109≤Ai≤109-10^9 \le A_i \le 10^9)。

  • 1 i x:AiA_i を xx に変更する。
  • 2 l r:(Al,…,Ar)(A_l, \dots, A_r) から、互いに重ならない空でない連続部分列を 00 個以上 22 個以下選ぶ。選んだ部分列の要素の総和の最大値を出力する。

連続部分列を 1 個選ぶ場合(最大部分配列問題)は、セグメント木の各ノードに「区間全体の和」「接頭辞の和の最大値」「接尾辞の和の最大値」「連続部分列の和の最大値」を持たせる方法が知られています。これを 2 個まで選べるように広げます。

ここで、長さ 00 の連続部分列(和は 00)も選べることにします。すると「00 個以上 22 個以下選ぶ」は「長さ 00 も含めてちょうど 22 個選ぶ」と同じになり、個数の場合分けが要らなくなります。

選ぶ連続部分列の個数 kk(k=1,2k = 1, 2)と、区間の端に接する部分列があるかどうかで、次の 8 つの値を持たせます。いずれも和の最大値です。

値左端から始まる部分列右端で終わる部分列
lrk\mathrm{lr}_kありあり
lk\mathrm{l}_kありなくてもよい
rk\mathrm{r}_kなくてもよいあり
zk\mathrm{z}_kなくてもよいなくてもよい

「左端から始まる部分列」は長さ 00 でもよいので、たとえば l1\mathrm{l}_1 は空の接頭辞も含めた接頭辞の和の最大値です。k=1k = 1 で左端から始まり右端で終わるのは区間全体なので、lr1\mathrm{lr}_1 は区間全体の和です。

隣り合う区間 XX(左)と YY(右)をつなげるときは、境目をまたぐ部分列があるかどうかで場合分けします。またぐ部分列は、XX の右端で終わる部分列と YY の左端から始まる部分列がつながったものです。そのため、個数は XX 側と YY 側の合計より 1 少なくなります。たとえば z2\mathrm{z}_2 は次の候補の最大値です。

  • 境目をまたがない:z2X\mathrm{z}_2^X、z2Y\mathrm{z}_2^Y、z1X+z1Y\mathrm{z}_1^X + \mathrm{z}_1^Y
  • 境目をまたぐ:r2X+l1Y\mathrm{r}_2^X + \mathrm{l}_1^Y、r1X+l2Y\mathrm{r}_1^X + \mathrm{l}_2^Y

ほかの値も同じように、「XX 側で左端の条件を満たし、YY 側で右端の条件を満たす」組み合わせを列挙すれば求まります。すべての部分列を長さ 00 にすれば和は 00 なので、lr1\mathrm{lr}_1 以外の値は 00 以上です。

全体の計算量は O(N+Qlog⁡N)O(N + Q \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/segtree.hpp"
struct AALC0001I {
struct S {
ll lr1, l1, r1, z1, lr2, l2, r2, z2;
S() {
lr1 = l1 = r1 = z1 = lr2 = l2 = r2 = z2 = 0;
}
S(ll a) {
lr1 = a;
l1 = r1 = z1 = lr2 = l2 = r2 = z2 = max(a, 0LL);
}
ll ans() const {
ll res = 0;
chmax(res, lr1);
chmax(res, l1);
chmax(res, r1);
chmax(res, z1);
chmax(res, lr2);
chmax(res, l2);
chmax(res, r2);
chmax(res, z2);
return res;
}
};
static S op(const S &a, const S &b) {
S res{};
res.lr1 = a.lr1 + b.lr1;
chmax(res.l1, a.l1);
chmax(res.l1, a.lr1 + b.l1);
chmax(res.r1, b.r1);
chmax(res.r1, a.r1 + b.lr1);
chmax(res.z1, a.z1);
chmax(res.z1, b.z1);
chmax(res.z1, a.r1 + b.l1);
chmax(res.lr2, a.l1 + b.r1);
chmax(res.lr2, a.lr1 + b.lr2);
chmax(res.lr2, a.lr2 + b.lr1);
chmax(res.l2, a.l2);
chmax(res.l2, a.lr1 + b.l2);
chmax(res.l2, a.lr2 + b.l1);
chmax(res.l2, a.l1 + b.z1);
chmax(res.r2, b.r2);
chmax(res.r2, a.r2 + b.lr1);
chmax(res.r2, a.r1 + b.lr2);
chmax(res.r2, a.z1 + b.r1);
chmax(res.z2, a.z2);
chmax(res.z2, b.z2);
chmax(res.z2, a.z1 + b.z1);
chmax(res.z2, a.r2 + b.l1);
chmax(res.z2, a.r1 + b.l2);
return res;
}
static S e() { return S(); }
};
void solve() {
LL(N, Q);
VL(A, N);
vec<AALC0001I::S> init;
init.reserve(N);
rep(i, N)
init.emplace_back(A[i]);
SegTree<AALC0001I> seg(init);
rep(Q) {
LL(q);
if (q == 1) {
LL(i, x);
seg.set(i - 1, {x});
} else if (q == 2) {
LL(l, r);
print(seg.prod(l - 1, r).ans());
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

SegTree には、要素の型 S、演算 op、単位元 e をまとめた構造体を渡します。op では結果を 00(すべて長さ 00 を選んだ場合)で初期化してから、chmax で候補を入れています。長さ 11 のノードでは、区間全体である lr1\mathrm{lr}_1 だけが AiA_i で、ほかの値は長さ 00 も選べるので max⁡(Ai,0)\max(A_i, 0) です。

使用ライブラリ:cpp_include@402f0cf

Blitz Round #25 B - Jump Trip Score

長さ nn の整数列 a1,…,ana_1, \ldots, a_n があり、位置 i=1i = 1 から出発して i=n+1i = n + 1 に着いたら終わりです。スコアは 00 から始まり、各位置で次のどちらかを行います。

  • aia_i をスコアに足して i+1i + 1 に進む
  • 正の整数 dd (i+d≤n+1i + d \le n + 1) を選んで i+di + d に跳ぶ(スコアは変わらない)

跳ぶ操作は高々 1 回まで使えるとき、最終スコアの最大値を求める問題です。

  • 1≤n≤4⋅1051 \le n \le 4 \cdot 10^5、−109≤ai≤109-10^9 \le a_i \le 10^9、テストケースの nn の総和は 4⋅1054 \cdot 10^5 以下

正確な問題文は元の問題ページを見てください。

ii から i+di + d に跳ぶと、ai,…,ai+d−1a_i, \ldots, a_{i+d-1} を飛ばすことになります。跳ぶのは高々 1 回なので、得られるスコアは

(先頭からの連続部分の和)+(末尾までの連続部分の和)(\text{先頭からの連続部分の和}) + (\text{末尾までの連続部分の和})

で、間の 1 区間を飛ばした形になります(跳ばなければ全部の和)。

そこで

  • LkL_k = 長さ kk 以下の接頭辞の和の最大値(空も含むので 00 以上)
  • RkR_k = 位置 k+1k + 1 以降から始まる接尾辞の和の最大値(空も含む)

を累積和で求めておけば、答えは

max⁡0≤k≤n(Lk+Rk)\max_{0 \le k \le n} (L_k + R_k)

です。接頭辞と接尾辞が重ならないように、境目 kk を全通り試しています。計算量は O(n)O(n) です。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int,input().split()))
dp0 = [0]
x = 0
for a in A:
x += a
dp0.append(max(x, dp0[-1]))
dp1 = [0]
x = 0
for a in reversed(A):
x += a
dp1.append(max(x, dp1[-1]))
dp1.reverse()
print(max(x+y for x,y in zip(dp0,dp1)))

dp0 が LL、dp1 が RR にあたります。