最大区間和の求め方4通り（DP/モノイド/累積和累積min/Kadane's Algorithm) - ぱるまの日記

↑と同じ内容

ARC174 A - A Multiply で最大区間和を求める問題が出てきました。

コンテスト後、最大区間和を求める方法がいくつかあるのを知りました。 この記事では最大区間和を求める方法を4つ紹介します。

以下、長さ n の整数配列 xs の最大区間和を求める問題を考えます。

定義

長さ n の整数配列 xs に対して、

xs の最大区間和 := max {xs[begin] + … + xs[end-1] | 0 ≤ begin ≤ end ≤ n}
xs の最大 prefix 和 := max {xs[0] + … + xs[end-1] | 0 ≤ end ≤ n}
xs の最大 suffix 和 := max {xs[begin] + … + xs[n-1] | 0 ≤ begin ≤ n}

と定義します。

1. 最大区間和DP

まずは最大区間和をDPで直接求める方法を説明します。

最大区間和のDPと最大 suffix 和のDPを以下で定義します

• dp_internal_sum[i] = [0, i) における最大区間和
  • これ単独だと漸化式が立たないので、以下の dp_suffix_sum が必要
• dp_suffix_sum[i] = [0, i) における最大 suffix 和

(i の範囲は 0 ≤ i ≤ n)

DPの初期値は以下の通りです。