配列内の整数の最大連続する合計を見つけるには

Question

私はこの実装を持っていますが、このプログラムの結果は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; 
} 

Answer 1

：

はデモのためにここを参照してください：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++) { 
    (...) 
} 

Answer 2

私はKadane's algorithmを示唆しています。あなたが正しいインデックスを使用していない

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; 
} 

Answer 3

それが探している場合はC++では、このような何か（未テスト）になりますインデックス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; 
    } 
} 

Answer 4

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

この問題のクイックフィックスは、最後のelseブロックにa[i] < 0 && temp_sum + t < 0がある場合に、temp sumを割り当てるときにチェックを追加することです。

} else if (i < n) { 
    temp_sum = a[i]; 
    if (temp_sum > max_sum) 
     max_sum = temp_sum; 
}