<< | к задаче | главная | печатать | обсудить(0 сообщений) >>
Задача: Подмножество с максимальной суммой
Исходник: Еще один линейный алгоритм [C++, code #629, hits: 8804, рейтинг: 3/7,4.88(2012)] +
аноним: Владимир [добавлен: 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

+добавить реализацию
 
каталог | задачи | паттерны | исходники | стат | форумы | карта сайта | контакты | ссылки 
© 2000-2017 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.015331 секунд
Количество запросов к БД: 9, gzip: 6.3kb/21.7kb(71%)