<< | к задаче | главная | печатать | обсудить(0 сообщений) >>
Задача: Подмножество с максимальной суммой
Исходник: Максимальная последовательность в массиве, квадратичный алгоритм №2 [C#, code #79, hits: 4757, рейтинг: 3/7,4.87(1989)] +
автор: this [добавлен: 28.02.2006] управление:
  1. public static int MaxSoFar_Quadro2(int[] arr)
  2. {
  3. int[] cumarr = new int[arr.Length];
  4. cumarr[0] = 0;
  5. for (int i = 1; i < arr.Length; i++)
  6. {
  7. cumarr[i] = cumarr[i - 1] + arr[i];
  8. }
  9.  
  10. int maxsofar = 0;
  11.  
  12. for (int i = 0; i < arr.Length; i++)
  13. {
  14. for (int j = i; j < arr.Length; j++)
  15. {
  16. int sum;
  17. if (i == 0) {
  18. sum = cumarr[j];
  19. } else {
  20. sum = cumarr[j] - cumarr[i - 1];
  21. }
  22. /* sum - сумма всех элементов arr[i..j] */
  23. maxsofar = Math.Max(maxsofar, sum);
  24. }
  25. }
  26.  
  27. return maxsofar;
  28. }
Производительность ~ O(n2)

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