走査アルゴリズムについて

質問

ｎ個の要素の配列ｘ[]について
配列ｘの連続した要素（部分配列）でその和が最大になるものを見つけて、
その和を出力するアルゴリズムについてです。

これなのですが解き方の考え方に

「x[0...n]までの部分配列の最大和は、x[0...n-1]の部分配列の最大和か、x[n]から左方向に伸びた配列の和のいずれかである。」

とあり

プログラムには
float maxSoFar(float x[], int length){
float maxsofar = 0;
float maxendinghere = 0;

for(int i = 0; i < length; i++){
maxendinghere = max(0.0f, maxendinghere + x[i]);
maxsofar = max(maxsofar, maxendinghere);
}

return maxsofar;
}
とあるのですが、アルゴリズムの仕組みがよくわかりません。
なぜ上のような説明でこのようにプログラムできるのかが
わからないので、どなたかうまい説明できる人お願いします＞＜

回答No.3

noname#50176 · ベストアンサー

<訂正>
誤：x[m]～x[n-1]までの連続した累積（0≦m≦n-1)
正：x[m]～x[p]までの間の連続した累積（0≦m＜p , 0＜p≦n-1）

<追記>
Ｑ．累積値とは具体的に何であるか？
Ａ．単にある時点の加算の合計です

<例> x[3]とした時、可能性として
・2つ以上の部分からなる、x[0]～[n-1]各部をつなげた累積
x[0] + x[2] = 合計和の最大値
・x[m]～x[p]までの間の連続した累積（0≦m＜p,0＜p≦n-1）
x[0] + x[1] = 合計和の最大値
x[1] + x[2] = 合計和の最大値
x[0] + x[1] + x[2] = 合計和の最大値

尚、累積値に負数を足した時は必ず最大値でなくなります。

お礼

たくさんのご説明ありがとうございました！
ちゃんと理解することができました！

なかなか難しいアルゴリズムですよね＞＜

回答No.4

bender

N個の要素を含む配列が与えられたとき、求めるような
『連続する』部分配列の最大和を探すためには、単純に
考えると、配列のs番目（0<=s<N）からはじまってe番目
(s<e<N)で終わるような部分配列すべてについて（つまり
N*(N+1)/2の部分配列について）、その和をひとつずつ
調べてみればよいわけですが、その方法では N が大きい
ときには結構な時間がかかります。

問題文にあるアルゴリズムのすごいところは、配列を
たった一回読み通す間に（つまり、一重のforループ
だけで）求める最大和が見つかるところだと思います。

> x[0...n]までの部分配列の最大和は、x[0...n-1]の
> 部分配列の最大和か、x[n]から左方向に伸びた
> 配列の和のいずれかである。

このヒントは、x[0...n]というn+1個の要素を含む配列が
与えられたとき、『連続する』部分配列のうちでその和が
最大となるようなものは、x[n]を含まない配列（すなわち
x[0...n-1]）の中にみつかるか、もしくはx[n]を含む
部分配列（すなわち「x[n]から左方向に伸びた配列」）で
あるかのいずれかである、といっています。

このヒントがいうことは、ある意味当たり前かもしれません。
というのも、x[0...n]のどんな部分配列も、x[0...n-1]の
部分配列か、x[n]から左に伸びる配列のいずれかでしか
あり得ないからです。とはいえ、このことから問題文に
あるような賢いプログラムが導かれます。

ヒントにある「x[0...i-1]の部分配列の最大和」がmaxsofarと
対応していて、「x[i]から左方向に伸びた配列の和」は
maxendinghere = max(0.0f, maxendinghere + x[i])　と対応
しているといえます。ただ、
maxendinghere = max(0.0f, maxendinghere + x[i]);
については、おそらく、
maxendinghere = max(x[i], maxendinghere + x[i]);
とした方がヒントに忠実であるように私は思います。

お礼

ありがとうございます！
すごいわかりやすかったです！

このオーダーｎはかなりビックリでした。

回答No.2

noname#50176

>あとおそらくちょっとこっちのミスだったと思うのですが
いえ、私も説明があやふやでしたので…。
>勘違いでしょうか・・？
勘違いではありません。

「x[0...n]までの部分配列の最大和は、x[0...n-1]の部分配列の最大和」
は、2つ以上の部分からなる、x[0]～[n-1]各部をつなげた累積で
「x[n]から左方向に伸びた配列の和」
は、x[m]～x[n-1]までの連続した累積（0≦m≦n-1）ですね。
失礼しました。

簡単に言えばこのアルゴリズム、
先頭から数値を累積していき、1つ前の累積より小さくなったら
前回、大きくなったら最新、の累積を最新のものとします。
これって、単にプラスの数値だけを足していくと言うことなんですよね…。

回答No.1

noname#50176

まずこのアルゴリズムの内容は次の流れになります。

１．n個のデータを用意
２．配列のx[n]を確保
x[n]確保は、x[0]～x[n-1]が使えます、これはご存知ですね。
x[3]と確保すれば、x[0],x[1],x[2] の３つですから、x[個数]です。
３．処理開始（下記参照）

＜処理内容＞
トレースチャートで示しますね（部分結果図の事）

float maxSoFar(float x[], int length){
float maxsofar = 0;累積値は最初０
float maxendinghere = 0;累積値は最初０

for(int i = 0; i < length; i++){
0～n-1=n回繰り返す
maxendinghere = max(0.0f, maxendinghere + x[i]);
0.0f（f=浮動小数記号）つまり0.0と現在累積値＋現在値を比較、
これで大きい方をmaxendinghere（現在累積値）に代入
（負数の場合は現在の累積を0.0に繰り上げるということ）
maxsofar = max(maxsofar, maxendinghere);
（最新累積値と現在累積値を比較し大きい方をmaxsofar（最新累積値）
に代入）
}
return maxsofar;
（最新累積値を返す）
}

（例）
・x[5] ５個確保する
x[0]=0.5 x[1]=0.2 x[2]=-0.6 x[3]=-0.9 x[4]=0.7
となっていた場合、
(cur=現在累積値 new=最新累積値 とします）
cur=0,new=0
0.0とcur+x[0]を比較
(0.0<0.0+0.5)でcur=0.5
newとcurを比較
(0.0<0.5)でnew=0.5
0.0とx[1]を比較
(0.0<0.5+0.2)でcur=0.7
newとcurを比較
(0.5<0.7)でnew=0.7
0.0とx[2]を比較
(0.0<0.7-0.6)でcur=0.1
newとcurを比較
(0.7>0.1)でnew=0.7
0.0とx[3]を比較
(0.0>0.7-0.9)でcur=0.0
newとcurを比較
(0.7>0.0)でnew=0.7
0.0とx[4]を比較
(0.0<0.7+0.7)でcur=1.4
newとcurを比較
(0.7<1.4)でnew=1.4

よって1.4が最大値です。
「x[0...n]までの部分配列の最大和は、x[0...n-1]の部分配列の最大和」
とは配列すべての合計値（x[n]は存在しない）
「x[n]から左方向に伸びた配列の和のいずれかである。」
とはx[0]～x[n-1] 内で任意の所の数値を足した値と考えます。

おそらく合っていると思います。

補足

すいませんたくさんの回答を＞＜ありがとうございます！

ただちょっと自分の聞き方でミスがあったようで
プログラム自体の計算の流れはわかっていて具体的な数列で
確かめたりしたのですが
なぜこのような計算方法でどんな理論でうまくいってるのか？が
わからなかったんです；；

教えてくださった回答では
・累積値とは具体的に何であるか？
と
最後の方に書いてある
＞x[0]～x[n-1] 内で任意の所の数値を足した値と考えます。
のところなどがちょっとわからないんです＞＜
どんな理論でこのような計算が立っているのか・・？

あとおそらくちょっとこっちのミスだったと思うのですが
「x[0...n]までの部分配列の最大和は、x[0...n-1]の部分配列の最大和」というのは、
ｘ[0..n]でｘ[n]は存在しませんがニュアンスとしては
最後の項を除いた配列の部分和の最大という意味で

「x[n]から左方向に伸びた配列の和のいずれかである。」とは
最後の項から左に向かって最大部分和を探した時の値～

といった感じかなと思ってたのですが・・・
勘違いでしょうか・・？