読者です 読者をやめる 読者になる 読者になる

本履歴

購入した古本の履歴と時々プログラミング

1次元配列中の連続した部分配列で和が最大となるものを求める

UVa: 11951 - Area

事の発端はこの問題(UVa Online Judge)。 長方形の数字の配置が与えられた時にサブ長方形で和が最大となるもの(ただしK以下)を求める問題。DP[x, y] = Sum(1, 1, x, y)を使ってO(N^2*M^2)の解法はTLEっぽいので、最終的に長方形の数字は全て正数であることから、

Sum(x1,y1,x2,y1)<Sum(x1,y1,x2,y1+1)<Sum(x1,y1,x2,y1+2)< ... <Sum(x1,y1,x2,M)

となり、この数列に対しK以下になるようバイナリサーチをしてO(N^2*M*log(M))でACとなり話はこれで終わりだったのですが・・・

Kadane's Algorithm

もっとうまい方法を模索していると1次元バージョンのMaximum subarray problem - Wikipedia, the free encyclopedia を発見。Kadane's algorithmと呼ばれているらしい。うーむ、沈思黙考、アハ、目からうろこが出た。以下私の翻訳。DPなんだけれど、配列Aの連続部分列で和が最大を求めるのに

DP[j]=A[i]+A[i+1]+...+A[j-1]+A[j]の最大値 for i=1 to j

と定義しこのDP[j]、すなわちおしまいの添字がjとなる連続部分列の中で最大和が分かったとすると

DP[1]=max{A[1], 0} //負の場合は取らないを選択
DP[j]=max{DP[j-1]+A[j],0} //負の場合は取らないを選択

が成り立つから、順次DPが求められて、元々欲しかった最大値はDPの中の最大値を返せばOKというアルゴリズム。これがうまく動くのが不思議ですがよく考えるとそうなる。最大の懸念点は、DP[j]=DP[j-1]+A[j]といえるのか、他にjで終わる連続部分列で最大のものがあるのではないかですが、あるとすると

DP[j-1]=A[i]+A[i+1]+...+A[j-1]
DP[ j ]=A[k]+A[k+1]+...+A[j-1]+A[j]

からA[i..k-1](or A[k..i-1])の部分和が負になる必要があり、DPの定義に矛盾するからそんなことはありえないi=kと言えます。 Rubyの実装は簡単。実は直前のdpの値しか使っていないのでdpという配列は省略できまス。それがwikipediaバージョンですね。実際の連続部分配列の箇所を求めたい時にはdpをアップデートする時にindex情報も保存すればOKです。

#!ruby
#O(n)
def kadane(ary)
    n = ary.size
    dp = Array.new(n + 1, 0) #index jで終わる部分配列の中での最大和
    n.times{|i|dp[i] = [dp[i - 1] + ary[i], 0].max}
    dp.max
end