Чтобы найти максимальную последовательную сумму целых чисел в массиве

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

Answer 3

Если он ищет наибольшая последовательная сумма, не начинающаяся с индекса 0, самым простым способом было бы иметь две петли

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

Индексы вашей реализации были неверными, как отмечают другие пользователи. Я чувствовал, что необходимо добавить ответ, однако, чтобы указать, что ваша реализация завершается с ошибкой, если все значения отрицательные (а число, близкое к положительному, не находится в первой позиции).

Быстрое решение этой проблемы заключается в том, чтобы добавить чек при назначении временной суммы в случае, когда 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; 
}