<< | к задаче | главная | печатать | обсудить(0 сообщений) >>
Задача: Подмножество с максимальной суммой
Исходник: Максимальная последовательность в массиве, алгоритм "разделяй и влавствуй" [C#, code #80, hits: 5276, рейтинг: 3/7,4.77(2195)] +
автор: this [добавлен: 28.02.2006] управление:
  1. public static int MaxSoFar_Recursion(int[] arr, int l, int u)
  2. {
  3. if (l > u)
  4. { /* Пустой массив */
  5. return 0;
  6. }
  7.  
  8. if (l == u)
  9. { /* 1 элемент */
  10. return Math.Max(0, arr[l]);
  11. }
  12.  
  13. int m = (l + u) / 2;
  14.  
  15. /* поиск макс. последовательности
  16. слева от границы: */
  17. int lmax = 0;
  18. int sum = 0;
  19. for (int i = m; i >= l; i--)
  20. {
  21. sum += arr[i];
  22. lmax = Math.Max(lmax, sum);
  23. }
  24.  
  25. /* поиск макс. последовательности
  26. справа от границы: */
  27. int rmax = sum = 0;
  28. for (int i = m + 1; i <= u; i++)
  29. {
  30. sum += arr[i];
  31. rmax = Math.Max(rmax, sum);
  32. }
  33.  
  34. return Math.Max(Math.Max(lmax + rmax,
  35. MaxSoFar.MaxSoFar_Recursion(arr, l, m)),
  36. MaxSoFar.MaxSoFar_Recursion(arr, m + 1, u));
  37. }
  38.  
  39. // Вызывается в виде:
  40. <object>.MaxSoFar_Recursion(myarr, 0, myarr.Length - 1);
Производительность ~ O(n*log n)

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