<< | к задаче | главная | печатать | обсудить(0 сообщений) >>
Задача: Подмножество с максимальной суммой
Исходник: Максимальная последовательность в массиве, наилучший линейный алгоритм [C#, code #81, hits: 5553, рейтинг: 3/7,4.85(2015)] +
автор: this [добавлен: 28.02.2006] управление:
  1. public static int MaxSoFar_Lin(int[] arr)
  2. {
  3. int maxsofar = 0;
  4. int maxendinghere = 0;
  5.  
  6. for (int i = 0; i < arr.Length; i++)
  7. {
  8. /* инвариант: значения maxendinghere и
  9. maxsofar точны для x[0..i-1] */
  10. maxendinghere = Math.Max(maxendinghere + arr[i], 0);
  11. maxsofar = Math.Max(maxendinghere, maxsofar);
  12. }
  13. return maxsofar;
  14. }
Производительность ~ O(n)

Самый быстрый алгоритм, предел производительности для данной задачи

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