0

二次最大連続サブシーケンス合計アルゴリズム

int maxSubSum2( const vector<int> & a)
{
  int maxSum = 0;
  for (int i = 0; i< a.size(); ++i)
  {
    int thisSum = 0;
    for (int j = i; j < a.size(); ++j)
    {
      thisSum += a[j];
      if (thisSum > maxSum)
        maxSum = thisSum;
    }
  }
  return maxSum;
}

アルゴリズムがどのように機能するかを誰かが説明できるかどうか疑問に思っていましたか? for ループは得意ですが、入れ子になったループは苦手です。「thisSum」は、8 行目の外側の for ループが実行されるたびに常に 0 ですか、それとも静的ですか?

どうもありがとうございました！私はアルゴリズムを理解するために一生懸命努力しています。私を助けてください！時間と労力を本当に感謝しています。

4

4 に答える 4

2

外側のループは、 vector のすべての要素を反復しますa。各反復iで、現在の要素のインデックスになり、 にリセットthisSumされ0、内側のループが実行されます。

内側のループは、 から始まるすべての要素を反復処理しますi。各反復でj、現在の要素のインデックスになります。次に、これらの要素の合計を で計算しthisSumます。

外側のループは、既に含まれているものよりも高い場合に置き換えmaxSumられます。thisSum

したがって、ベクトルに次が含まれている場合:

1 7 -10 2 4

外側のループの連続する反復により、次の の値が計算されますthisSum。

1 + 7 + -10 + 2 + 4 = 4
7 + -10 + 2 + 4 = 3
-10 + 2 + 4 = -4
2 + 4 = 6
4 = 4

maxSumに設定される最初の反復4。2 回目と 3 回目の反復後はthisSum > maxSumfalse になるため、変更されません。4 回目の反復では6 > 4、 に設定さmaxSumれ6ます。最後の反復はそれを変更しません。最後に、それは戻り6ます。

于 2015-01-09T01:17:05.800 に答える
0

外側の for ループがループするたびに、 が外側のループ=0の最初の行にあるため、この合計は 0 にリセットされます。

関数を変更して、内側のループで i、j、および thisSum を出力し、それらがどのように変化しているかを確認することをお勧めします。

于 2015-01-09T01:15:47.317 に答える
0

コード行 8 の thisSum は、ループiの開始部分でリセットされます。

しかし、ループ j の thisSum は、ループ j に配列 a[ ] 要素を追加し続けています。

通常、ループがどのように機能するかを理解するために、値を置き換えて値を想定します。

ベクトル a に 3 つの int 要素 10,-2​​0,100 があると仮定します

したがって、a.size() = 3

//maxSum is initialized in the function
int maxSum = 0;

//Start First i loop
int i = 0; i < 3; 
int thisSum = 0; 

int j = i = 0; j < 3; 
thisSum += a[0];
//thisSum = 10
//10 > 0
if (thisSum > maxSum) maxSum = thisSum = 10;
int j = i = 1; j < 3; 
thisSum += a[1];
//thisSum = -10
// -10 not > 10
int j = i = 2; j < 3; 
thisSum += a[2];
//thisSum = 90
//90 > 10
if (thisSum > maxSum) maxSum = thisSum = 90;
//End First i loop

//Start 2nd i loop
int i = 1; i < 3; 
int thisSum = 0; 

int j = i = 1; j < 3; 
thisSum += a[1];
//thisSum = -20
//-20 not > 90
int j = i = 2; j < 3; 
thisSum += a[2];
//thisSum = 80
//80 not > 90
//End 2nd i loop

//Start 3rd i loop
int i = 2; i < 3; 
int thisSum = 0; 

int j = i = 2; j < 3; 
thisSum += a[2];
//thisSum = 100
//100 > 90
if (thisSum > maxSum) maxSum = thisSum = 100;
//End 3rd i loop

//return 100
//return maxSum

関数の概念は、最小のインデックス要素から最大のインデックス引数までアイテムを段階的に削除して、最大合計を取得しようとすることです。

1 回目のループ i : maxSum = 90

2 番目のループ i : maxSum = 90 (10 を削除)

3 番目のループ i : maxSum = 100 (10、-20 を削除)

于 2015-01-09T01:59:37.463 に答える
0

例 a = [1, 2, 3, 4, 5]

j は i の値から始まるため、最初は 0 から始まり、次に 1、次に 2 と続きます。したがって、この 2 番目の内側のループは、外側のループがインクリメントするたびに小さくなります。

thisSum は静的ではないため、毎回 0 にリセットされます。もしそうなら、それは静的とラベル付けされます。

基本的に、このアルゴリズムでは、外側のループを使用して「開始インデックス」を前方にプッシュし、内側のループを使用して配列/ベクトルのすべての要素を実際に追加します。

したがって、上記の例の内部ループの実行は次のようになります。

Execution 1: 1 + 2 + 3 + 4 + 5
Execution 2: 2 + 3 + 4 + 5
Execution 3: 3 + 4 + 5
Execution 4: 4 + 5
Execution 5: 5

それが役立つことを願っています。

于 2015-01-09T01:23:10.967 に答える