長さ 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_internal_sum 単独だと漸化式が立たないので、dp_suffix_sum が必要
  • dp_suffix_sum[i] = [0, i) における最大 suffix 和

  i の範囲は 0 ≤ i ≤ n)

• DPの初期値

  • dp_internal_sum[0] = 0
  • dp_suffix_sum[0] = 0

• DPの漸化式は以下の通りです。

  • dp_internal_sum[i+1] = max(dp_internal_sum[i], dp_suffix_sum[i] + xs[i])
    • xs[i] を使うかどうかで場合分け
  • dp_suffix_sum[i+1] = max(xs[i], dp_suffix_sum[i] + xs[i])
    • [0, i) を使うかどうかで場合分け

• コード

2. 最大区間和モノイド

以下の4つの情報を元に持つモノイドを考える

• 和
• 最大区間和
• 最大 prefix 和
• 最大 suffix 和