3

この実装があります。このプログラムの結果は 100 ですが、正解は 103 です。この実装の何が問題なのか、または配列内の整数の最大連続合計を見つけるためのより良い方法があるかどうかを知っている人はいますか?

前もって感謝します。 

#include <stdio.h>

int main(void) {
int a[] = { -3, 100, -4, -2, 9, -63, -200, 55 };
int max_sum, temp_sum, i, n = 12, t;
temp_sum = max_sum = a[0];
for (i = 1; i < n; i++) {
    if (a[i] > 0)
        temp_sum += a[i];
    else {
        t = 0;
        while (a[i] < 0 && i < n) {
            t += a[i];
            i++;
        }
        if (temp_sum + t > 0) {
            temp_sum = temp_sum + t + a[i];
            if (temp_sum > max_sum)
                max_sum = temp_sum;
        } else if (i < n)
            temp_sum = a[i];
    }
}
if (temp_sum > max_sum)
    max_sum = temp_sum;
printf("Maximum Numbers is %d \n", max_sum);
return 0;
}
4

4 に答える 4

6

正しいインデックスを使用していません：

デモについてはこちらをご覧ください：http：//codepad.org/wbXZY5zP

int max_sum, temp_sum, i, n = 8, t;
temp_sum = max_sum = a[0];
for (i = 0; i < n; i++) {
    (...)
}
于 2012-04-10T19:54:58.187 に答える
4

かだねのアルゴリズムをお勧めします。C ++では、次のようになります（テストされていません）。 

int maxSubarray(std::vector<int> a) {
    int maxAll = 0, maxHere = 0;
    for (size_t i = 0; i < a.size(); ++i) {
        maxHere = std::max(a[i], maxHere + a[i]);
        maxAll = std::max(maxAll, maxHere);
    }
    return maxAll;
}
于 2012-04-10T19:54:39.527 に答える
1

他のユーザーが指摘したように、実装のインデックスが正しくありませんでした。ただし、すべての値が負の場合 (および正に最も近い数が最初の位置にない場合) に実装が失敗することを指摘するために、回答を追加する必要があると感じました。

a[i] < 0 && temp_sum + t < 0この問題の簡単な解決策は、最後の else ブロックで - の場合に一時的な合計を割り当てるときにチェックを追加することです。

} else if (i < n) {
    temp_sum = a[i];
    if (temp_sum > max_sum)
       max_sum = temp_sum;
}
于 2012-04-10T20:12:35.040 に答える
0

インデックス0から始まらない最大の連続合計を探している場合、最も簡単な方法は2つのループを持つことです。

int max_sum, temp_sum, i, n = 8, t;
max_sum = a[0];
for (t = 0; t < n; t++) {
    temp_sum = 0;
    for (i = t; i<n; i++) {
        temp_sum += a[i];
        if (temp_sum > max_sum)
            max_sum = temp_sum;
    }
}
于 2012-04-10T20:06:11.627 に答える