前提知識

Kadane's Algorithm | 最大部分配列 問題 - Ark's Blog

DPについて調べてたらKadane's algorithmという聞いたことないアルゴリズムが出てきたので調べてみた。 Kadane's algorithmは、最大部分配列問題(maximum subarray problem)をで解くアルゴリズムみたいです。 以下は、最大部分配列問題とそれを解くアルゴリズムの解説です。

https://ark4rk.hatenablog.com/entry/2018/01/08/002508

これを事前に読んで欲しいです

方法

分割統治法の方針でセグ木に乗せられます
これにより、

• 点更新
• [l,r)間の連続部分列における総和の最大値を求める
  が出来ます

( (左端を含む最大部分配列),(右端を含む最大部分配列),(区間の最大部分配列),(区間の総和))
からなるベクトルを考えると、これがモノイドになっています。

試しにベクトル $s$ とベクトル $t$ をくっつけて $s\times t$ を作ってみます。

• $s\times t$ の(左(右)端を含む最大部分配列):
  (sの左端を含む最大部分配列)
(sの区間の総和)+(tの左端を含む最大部分配列)
  の 2 つが条件を満たすので、max を取ります
  右端も同様です

• $s\times t$ の区間の最大部分配列:
  中央をまたぐやつとまたがないやつを考える分割統治法の王道により
  (sの最大部分配列)
(tの最大部分配列)
(sの右端を含む最大部分配列)+(tの左端を含む最大部分配列)
  の max です

• $s\times t$ の総和:
  (sの総和)+(tの総和)
  それはそう

よって上手くセグ木に乗せられます(モノイドの要件を満たすのは意味論より明らか)

ps.この方法によって $s \times t \times u=\max(0,\max(0,s+t),u)$ みたいな演算をモノイドとして処理出来たりもします(kadane のアルゴリズムより)