「整数の 1 次元配列内の連続する部分配列の最大和を見つける効率的な C プログラムを作成してください。配列の連続する部分配列は、任意の連続した集合に含まれる要素のシーケンスとして定義されます。配列内で有効なインデックス。
配列 {5,-3, 4} の例を見てみましょう。可能な連続した部分配列の組み合わせは、{5}、{-3}、{4}、{5,-3}、{-3,4}、および {5,-3,4} です。5 と 4 のインデックスは連続していないため、{5,4} は有効な部分配列ではないことに注意してください。連続する部分配列 {5,-3,4} の最大合計は 6 です。"
私はそれを解決しようとしましたが、問題を理解していないことに気付きました.5つの異なる値の配列がある場合、結果は10になるはずですが、15（5つの異なる要素+全体として1 + 4要素2 x 2 + 3 x 3 x 3 + 2 x 4 x 4)。
それを (C で) コーディングしようとする前に、誰かが問題自体を理解するのを手伝ってくれるかどうか知りたいです。
これが私が問題を解決する方法です。これは必ずしも最適な解決策ではありませんが、うまくいくはずです。
配列 {1, -2, 3, 5, -4} を考えて、すべてのサブ配列を手動で記述する方法を検討してください。
最大の合計は 8 のようです。
配列の長さ (この場合は 5) から始めて、1 要素配列を処理するまで長さを 1 減らしたパターンがここに表示されます。また、配列の 0 番目の要素から始めて、長さを指定して有効な配列を作成しようとしました。たとえば、配列要素 0 から始まる 4 つの要素の配列で作業していた場合、配列 [0] -> 配列 [3] および配列 [1] -> 配列 [4] を介してサブ配列を作成できます (これはPython などの一部の言語には、配列スライスを実行するための明示的な表記法がありますが、C にはありません)。各スライスを生成した後、要素を合計し、完了したら最大値を探します。
さて、私はこれを次のようにコーディングします
int main(void)
{
int array[] = {1, -2, 3, 5, -4};
int max = -1; // will hold largest sum
int len = sizeof(array)/sizeof(int); // C-idiom to find length of array
for(int slen = len; slen > 0; slen--) // loop for length of sub-arrays
{
for(int jdx = 0; jdx+slen <= len; jdx++) // looping over elements in original array
{
int temp = calcSum(array, jdx, slen);
if(temp > max)
max = temp;
}
}
printf("maximum sum of sub-array is: %d\n", max);
}
あとはcalcSum関数を書くだけです。これは 3 つのパラメーターを取ります。1 つ目は元の配列、2 つ目はサブ配列の開始位置、これはサブ配列の長さです。
int calcSum(int* array, int start, int len)
{
int sum = 0;
printf("[%d:%d]: {", start, start+len);
for(int ndx = 0; ndx < len; ndx++)
{
printf("%d,", array[start+ndx]);
sum = sum + array[start+ndx];
}
printf("} the sum is %d\n", sum);
return sum;
}
そこにいくつかの printf を散りばめたので、プログラムがループするときに何が起こっているかがわかります。私のスライス表記は [start:length] なので、[1:3] はインデックス 1 から始まり、長さが 3 の配列になります (つまり、配列 [1]、配列 [2]、配列 [3])。
上記を as としてコンパイルし、gcc -std=c99 -pedantic -Wall test.c -o tempこれを実行すると、次の結果が得られます。
D:\Users\******\GNUHome>temp.exe
[0:5]: {1,-2,3,5,-4,} the sum is 3
[0:4]: {1,-2,3,5,} the sum is 7
[1:4]: {-2,3,5,-4,} the sum is 2
[0:3]: {1,-2,3,} the sum is 2
[1:3]: {-2,3,5,} the sum is 6
[2:3]: {3,5,-4,} the sum is 4
[0:2]: {1,-2,} the sum is -1
[1:2]: {-2,3,} the sum is 1
[2:2]: {3,5,} the sum is 8
[3:2]: {5,-4,} the sum is 1
[0:1]: {1,} the sum is 1
[1:1]: {-2,} the sum is -2
[2:1]: {3,} the sum is 3
[3:1]: {5,} the sum is 5
[4:1]: {-4,} the sum is -4
maximum sum of sub-array is: 8
注意: Windows 7 Professional で gcc バージョン 4.8.3 (mingw から) を使用してこれをコンパイルしました。