<< | к задаче | главная | печатать | обсудить(0 сообщений) >>
Задача: Подмножество с максимальной суммой
Псевдокод: Рекурсивный, быстрый вариант управление:
  1. function maxsum(l, u)
  2. if l > u
  3. return 0 /* пустой массив */
  4. if l == u /* 1 элемент */
  5. return max(0, x[l])
  6. m = (l + u) / 2
  7.  
  8. /* поиск макс. последовательности
  9. слева от границы: */
  10. lmax = sum = 0
  11. for i = m downto l
  12. sum += x[i]
  13. lmax = max(lmax, sum)
  14.  
  15. /* поиск макс. последовательности
  16. СПРАВА от границы: */
  17. rmax = sum = 0
  18. for i = m + 1 to u-1
  19. sum += x[i]
  20. rmax = max(rmax, sum)
  21.  
  22. return max(lmax+rmax, // =>Mc
  23. maxsum(l, m) // =>Ma
  24. maxsum(m+1, u)) // =>Mb
  25.  
  26. /* А теперь запуск всего алгоритма */
  27. answer = maxsum(0, n-1)

 
каталог | задачи | паттерны | исходники | стат | форумы | карта сайта | контакты | ссылки 
© 2000-2018 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.002826 секунд
Количество запросов к БД: 3, gzip: 2.7kb/8.4kb(69%)