de kadane encontrar subarreglo con la suma máxima

Question

tengo la siguiente implementación de Kadane's algorithm para resolver el problema de la subserie máximo de una matriz:

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

se produce un error cuando se utiliza una secuencia que comienza con un negativo número como -1, 2, 3 dando un resultado de 4, [0,2] en lugar de 5, [1,2].

Por la vida de mí que no puedo encontrar dónde está el error. Tal vez es un defecto en el diseño del algoritmo?

Gracias de antemano.

Answer 1

Su implementación inicial sufrió de cheques innecesariamente complicadas y parcialmente erróneos dentro de la exploración principal ciclo.Estas comprobaciones son dos:

• si se encuentra un intermedio mayor sum, guárdelo como un resultado temporal;
• de forma independiente, si sum tiene negativo, reinícielo a 0 y prepárese para crear una nueva secuencia a partir de la siguiente posición de escaneo.

refactorizado FindBestSubsequence implementación del método se enumeran a continuación:

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

Ahora no sólo para -1,2,3 el código anterior produce respuesta correcta 5,[1,2] sino que también procesa correctamente los conjuntos de todos los números negativos sin ningún código adicional: entrar -10,-2,-3 devolverá -2,[1,1].

Answer 2

En su ejemplo, siempre tiene sum > result aunque sum<0 en la primera iteración de The loop porque 0 > decimal.MinValue.

Así que nunca vaya a su segunda case.-

Es necesario cambiar el primer caso mediante la adición de una condición sum > 0:

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

Actualización:

Como se ha explicado en mi comentar que solo puede cambiar la inicialización del resultado a 0:

decimal result = 0; 

de Wikipedia:

Este subconjunto está vacío (en cuyo caso su suma es cero) o consiste en un elemento más de la submatriz máximo terminando en la posición anterior

Por lo tanto si el matriz contiene sólo números negativos la solución es una submatriz vacío con suma 0.

Answer 3

cambiar esta línea:

decimal result = decimal.MinValue; 

a

decimal result = 0; 

Answer 4

Para cada posición que debe tomar el máximo del valor de allí (de la secuencia original) y su suma como lo ha escrito. Si el número original es más grande, entonces es mejor comenzar a sumar 'desde el principio', es decir, sum = max(sum+tempList[index],tempList[index]); Entonces no necesitará el caso para la suma < 0 en absoluto.

Answer 5

Al final esto es como he corregido el algoritmo para manejar todas las situaciones, en caso de que ayuda a alguien:

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

construido sobre answer y comentarios 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; 
    }