Задача: Найти максимальную сумму в последовательности
Исходник: Еще один линейный алгоритм поиска максимальной суммы последовательности элементов в массиве, язык: C++ [code #629, hits: 13018]
аноним: Владимир [добавлен: 25.09.2011]
  1. #include <stdio.h>
  2.  
  3. #define min(a,b) (((a) < (b)) ? (a) : (b));
  4. #define max(a,b) (((a) > (b)) ? (a) : (b));
  5.  
  6.  
  7. int main(void)
  8. {
  9. int ar[] = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84}; // Наш массив.
  10. int size = sizeof(ar) / sizeof(ar[0]); // Определяем его размер.
  11.  
  12. int result = 0; // Сюда поместим результат.
  13. int minSum = 0; // Сюда будем класть минимальную сумму элементов [0..i-1] внутри цикла.
  14. int curSum = 0; // Сюда будем накапливать сумму элементов [0..i], S(i).
  15.  
  16. for (int i = 0; i < size; ++i)
  17. {
  18. minSum = min(minSum, curSum);
  19. curSum += ar[i];
  20. result = max(result, curSum - minSum);
  21. }
  22.  
  23. // Выводим результаты.
  24. printf("\nMaximum summ = %d\n", result);
  25.  
  26. return 0;
  27. }
Вот тут есть альтернативный линейный алгоритм:
http://volodka.0fees.net/codesamples/sample_001.html

+добавить реализацию