Задача: Найти максимальную сумму в последовательности
Исходник: "разделяй и влавствуй", язык: C# [code #80, hits: 7535]
автор: 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)
Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

+добавить реализацию