di Kadane per trovare sottoarray con la somma massima

Question

Ho la seguente implementazione di Kadane's algorithm per risolvere il problema del sottoarray massima di un array:

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; 
} 

fallisce quando uso una sequenza che inizia con un negativo numero come -1, 2, 3 dando un risultato di 4, [0,2] anziché 5, [1,2].

Per la vita di me che non riesco a trovare dove sia l'errore. Forse è un difetto nella progettazione dell'algoritmo?

Grazie in anticipo.

Answer 1

L'implementazione iniziale soffriva di controlli inutilmente complicato e in parte sbagliate all'interno della scansione principale ciclo.Questi controlli sono due:

• se viene rilevato un intermedio maggiore sum, memorizzarlo come risultato temporaneo;
• in modo indipendente, se sum è negativo, reimpostarlo su 0 e prepararsi a creare una nuova sequenza dalla successiva posizione di scansione.

refactoring FindBestSubsequence implementazione del metodo è riportato di seguito:

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; 
} 

Ora non solo per -1,2,3 il codice precedente produce risposta corretta 5,[1,2] ma anche elabora correttamente array di tutti i numeri negativi senza alcun codice aggiuntivo: entrando -10,-2,-3 restituirà -2,[1,1].

Answer 2

Nel tuo esempio hai sempre sum > result anche se sum<0 nella prima iterazione del ciclo perché 0 > decimal.MinValue.

Così non si va al secondo case.-

È necessario modificare il primo caso con l'aggiunta di una condizione sum > 0:

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

Aggiornamento:

Come spiegato nel mio commento è possibile solo modificare l'inizializzazione del risultato su 0:

decimal result = 0; 

Da wikipedia:

Questo sottomatrice è vuota (nel qual caso la sua somma è zero) o consiste di un elemento più della sottomatrice massima termina alla precedente posizione

Pertanto, se la array contiene solo numeri negativi la soluzione è una sottomatrice vuota con somma 0.

Answer 3

Modifica questa linea:

decimal result = decimal.MinValue; 

a

decimal result = 0; 

Answer 4

Per ogni posizione si dovrebbe prendere il massimo del valore lì (dalla sequenza originale) e la vostra somma come avete scritto. Se il numero originale è più grande, allora è meglio iniziare a sommare 'dall'inizio', cioè sum = max(sum+tempList[index],tempList[index]); Quindi non sarà necessario il caso per somma < 0.

Answer 5

Alla fine questo è come ho corretto l'algoritmo per gestire tutti gli scenari, nel caso in cui esso contribuisce a qualcuno:

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

costruita su answer e commenti Gene Belitski s':

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; 
    }