Задача: Найти максимальную сумму в последовательности
Исходник: Линейный, самый быстрый алгоритм, язык: C# [code #81, hits: 7905]
автор: 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)

Самый быстрый алгоритм, предел производительности для данной задачи
Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

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