Kadaně, aby znaleźć subarray z maksymalną sumą

Question

Mam następujący realizację Kadane's algorithm rozwiązać problem maksymalnego subarray tablicy:

public static decimal FindBestSubsequence 
    (this IEnumerable<decimal> source, out int startIndex, out int endIndex) 
{ 
    decimal result = decimal.MinValue; 
    decimal sum = 0; 
    int tempStart = 0; 

    List<decimal> tempList = new List<decimal>(source); 

    startIndex = 0; 
    endIndex = 0; 

    for (int index = 0; index < tempList.Count; index++) 
    { 
     sum += tempList[index]; 
     if ((sum > result) || 
      (sum == result && (endIndex - startIndex) < (index - tempStart))) 
     { 
      result = sum; 
      startIndex = tempStart; 
      endIndex = index; 
     } 
     else if (sum < 0) 
     { 
      sum = 0; 
      tempStart = index + 1; 
     } 
    } 

    return result; 
} 

zawiedzie, gdy używam sekwencję, która zaczyna się negatywna numer taki jak -1, 2, 3, podając wynik 4, [0,2] zamiast 5, [1,2].

Za życie mnie nie mogę znaleźć, gdzie jest błąd. Być może jest to defekt w konstrukcji algorytmu?

Z góry dziękuję.

Answer 1

Początkowe wdrożenie cierpiał niepotrzebnie skomplikowanych i częściowo niewłaściwych kontroli wewnątrz głównego skanowania cykl.Kontrole te to dwa:

• jeśli znaleziono większy związek pośredni sum, zapisz jego składniki jako wynik tymczasowy;
• niezależnie, jeśli sum uzyskał wartość ujemną, zresetuj go na 0 i przygotuj się do zbudowania nowej sekwencji z następnej pozycji skanowania.

refactored FindBestSubsequence realizacja metoda znajduje się na liście poniżej:

public static decimal FindBestSubsequence (this IEnumerable<decimal> source, out int startIndex, out int endIndex) 
{ 
    decimal result = decimal.MinValue; 
    decimal sum = 0; 
    int tempStart = 0; 

    List<decimal> tempList = new List<decimal>(source); 

    startIndex = 0; 
    endIndex = 0; 

    for (int index = 0; index < tempList.Count; index++) 
    { 
     sum += tempList[index]; 
     if (sum > result) 
     { 
      result = sum; 
      startIndex = tempStart; 
      endIndex = index; 
     } 
     if (sum < 0) 
     { 
      sum = 0; 
      tempStart = index + 1; 
     } 
    } 

    return result; 
} 

Teraz nie tylko dla -1,2,3 Powyższy kod tworzy poprawną odpowiedź 5,[1,2] ale również prawidłowo przetwarza tablice wszystkich ujemnych liczb bez dodatkowego kodu: wprowadzając -10,-2,-3 zwróci -2,[1,1].

Answer 2

W twoim przykładzie zawsze masz sum > result nawet jeśli sum<0 w pierwszej iteracji pętli, ponieważ 0 > decimal.MinValue.

Więc nigdy nie iść do drugiego case.-

trzeba zmienić jeśli pierwszy dodając warunek sum > 0:

if ((sum >0) & ((sum > result) || 
    (sum == result && (endIndex - startIndex) < (index - tempStart)))) 
{ 
    ... 
} 
else if (sum < 0) 
{ 
    ... 
} 

Aktualizacja:

Jak wyjaśniono w moim komentarz można po prostu zmienić inicjalizację wyniku na 0:

decimal result = 0; 

Z Wikipedii:

Ten subarray jest albo pusta (w tym przypadku jego suma wynosi zero) lub składa się z jeszcze jednym elemencie niż maksymalna subarray kończącym się na poprzednim stanowisku

Dlatego jeśli tablica zawiera tylko liczby ujemne rozwiązanie jest pusty subarray z sumą 0.

Answer 3

zmienić tę linię:

decimal result = decimal.MinValue; 

do

decimal result = 0; 

Answer 4

Dla każdej pozycji należy wytrzymać maksymalne wartości tam (z oryginalnej sekwencji) i swoją sumę jak masz napisać. Jeśli pierwotny numer jest większy, lepiej zacząć od sumowania "od początku", tj. sum = max(sum+tempList[index],tempList[index]); Wtedy nie będziesz potrzebował przypadku dla sumy < 0 w ogóle.

Answer 5

Pod koniec tego właśnie poprawiłem algorytm do obsługi wszystkich scenariuszy, na wszelki wypadek, że pomaga komuś:

public static decimal FindBestSubsequence (this IEnumerable<decimal> source, out int startIndex, out int endIndex) 
    { 
     decimal result = decimal.MinValue; 
     decimal sum = 0; 
     int tempStart = 0; 

     List<decimal> tempList = new List<decimal>(source); 

     if (tempList.TrueForAll(v => v <= 0)) 
     { 
      result = tempList.Max(); 
      startIndex = endIndex = tempList.IndexOf(result); 
     } 
     else 
     { 
      startIndex = 0; 
      endIndex = 0; 

      for (int index = 0; index < tempList.Count; index++) 
      { 
       sum += tempList[index]; 

       if (sum > 0 && sum > result || (sum == result && (endIndex - startIndex) < (index - tempStart))) 
       { 
        result = sum; 
        startIndex = tempStart; 
        endIndex = index; 
       } 
       else if (sum < 0) 
       { 
        sum = 0; 
        tempStart = index + 1; 
       } 
      } 
     } 

     return result; 
    } 

Answer 6

Zbudowany na Gene Belitski „s answer i komentarze:

public static void Main() 
    { 
     var seq = new[] { -10M, -2M, -3M }; 
     var stuff = seq.FindBestSubsequence(); 

     Console.WriteLine(stuff.Item1 + " " + stuff.Item2 + " " + stuff.Item3); 
     Console.ReadLine(); 
    } 

    public static Tuple<decimal, long, long> FindBestSubsequence(this IEnumerable<decimal> source) 
    { 
     var result = new Tuple<decimal, long, long>(decimal.MinValue, -1L, -1L); 

     if (source == null) 
     { 
      return result; 
     } 

     var sum = 0M; 
     var tempStart = 0L; 
     var index = 0L; 

     foreach (var item in source) 
     { 
      sum += item; 
      if (sum > result.Item1) 
      { 
       result = new Tuple<decimal, long, long>(sum, tempStart, index); 
      } 

      if (sum < 0) 
      { 
       sum = 0; 
       tempStart = index + 1; 
      } 

      index++; 
     } 

     return result; 
    }