Encuentra la suma de intervalo máxima en una lista de números reales

Question

Aquí hay una pregunta de la entrevista que un colega pidió para un puesto de programación. Pensé que esto era genial para ver al entrevistado reflexionar. Me encantaría recibir respuestas sobre cómo lo piensa la comunidad SO.

dado una lista de los números reales de longitud N, dicen [a_1, a_2, ..., a_N], ¿cuál es la complejidad de encontrar el valor máximo M para el cual no existen índices 1 < = i < = j < = N tal que

a_i + a_{i+1} + ... + a_j = M?

Mis disculpas si esto es un problema clásico de CS.

Answer 1

La complejidad es just O(n) for Kadane's algorithm:

El algoritmo mantiene un registro de la subsecuencia máxima tentativa en (maxSum, maxStartIndex, maxEndIndex). Se acumula una suma parcial en currentMaxSum y actualiza el rango óptimo cuando esta suma parcial llega a ser mayor que maxSum.

Answer 2

Esto podría estar mal porque es sospechosamente simple.

1. Comience sumando todos los elementos de 0 a n, y determine el índice donde la suma móvil fue la más alta. Este será el límite superior de su intervalo.
2. Haz lo mismo al revés para obtener tu límite inferior. (Es suficiente si comienza desde el límite superior).

Esto se ve como O (n).

Answer 3

Es O(N):

int sum = 0; 
int M = 0; // This is the output 
foreach (int n in input) { 
    sum += n; 
    if (sum > M) 
     M = sum; 

    if (sum < 0) 
    sum = 0; 
} 

La idea es mantener la suma de todos los números enteros que se han encontrado desde el último reinicio. Se produce un reinicio cuando la suma va por debajo de cero, es decir, hay demasiados números negativos en el intervalo actual para que sea posiblemente el mejor.

Answer 4

Prueba este código .. que funcionaría bien para al menos un + ve número en la matriz .. O (n) sólo uno de bucle utilizado ..

public static void main(String[] args) { 
    int length ; 
    int a[]={-12, 14, 0, -4, 61, -39}; 
    length=a.length; 

    int absoluteMax=0, localMax=0, startIndex=0, lastIndex=0, tempStartIndex=0; 
    for (int index=0;index<length;index++) { 
     localMax= localMax + a[index]; 
     if(localMax < 0){ localMax=0; tempStartIndex = index + 1;} 
     if(absoluteMax < localMax) { 
      absoluteMax = localMax; 
      lastIndex =index; 
      startIndex=tempStartIndex; 
     } 
    } 

    System.out.println("startIndex "+startIndex+" lastIndex "+ lastIndex);  
    while (startIndex <= lastIndex) { 
     System.out.print(" "+a[startIndex++]); 
    } 
} 

Answer 5

Este es un clásico, bien conocido , problema que es una excelente revelación en cualquier curso de algoritmo. Es difícil encontrar un arranque mejor/más simple. Puede encontrar un n * 3-, n * 2-, nlogn- e incluso el simple n-algoritmo.

Encontré el problema discutido/resuelto en "Programming Pearls" de John Bentley desde 1986 - y lo utilicé durante años como iniciador en nuestro Curso de Algoritmo en NTNU/Trondheim. Hace unos 20 años, lo usé por primera vez en un examen para unos 250 estudiantes, donde solo 1 estudiante descubrió las 4 soluciones, ver más arriba. Él, Bjørn Olstad, se convirtió en el "profesor más joven de todos" en NTNU en Trondheim, y todavía tiene este estatus además de dirigir la división de búsqueda de MSFT en Oslo. Bjørn también tomó el desafío de encontrar buenas aplicaciones prácticas del algoritmo. ¿Ves algo?

• Arne Halaas

Answer 6

estoy entrometerse en este antiguo hilo de dar una explicación detallada de por qué funciona el algoritmo de kadane. El algoritmo fue presentado en una clase que estoy tomando actualmente, pero con solo una vaga explicación. Aquí está una implementación del algoritmo en Haskell:

maxCont l = maxCont' 0 0 l 

maxCont' maxSum _ [] = maxSum 
maxCont' maxSum thisSum (x:xs) 
    | newSum > maxSum = maxCont' newSum newSum xs 
    | newSum < 0  = maxCont' maxSum 0 xs 
    | otherwise  = maxCont' maxSum newsum xs 
    where 
    newSum = thisSum + x 

Ahora ya sólo estamos tratando de entender el algoritmo, vamos a deshacer la optimización de menor importancia de nombrar newSum:

maxCont l = maxCont' 0 0 l 

maxCont' maxSum _ [] = maxSum 
maxCont' maxSum thisSum (x:xs) 
    | thisSum + x > maxSum = maxCont' (thisSum + x) (thisSum+x) xs 
    | thisSum + x < 0  = maxCont' maxSum 0 xs 
    | otherwise   = maxCont' maxSum (thisSum+x) xs 

¿Cuál es esta función loca maxCont' ? Vamos a dar con una simple especificación de lo que se supone que debe hacer. Queremos que el siguiente para sostener, con la condición de que 0 ≤ thisSum ≤ maxSum:

maxCont' maxSum thisSum [] = maxSum 
maxCont' maxSum thisSum l = maximum [maxSum, thisSum + maxInit l, maxCont l] 

donde maxInit l es la mayor suma de un segmento inicial de l y maxCont es la suma máxima contigua de l.

Hecho trivial pero importante: para todos l, maxInit l ≤ maxCont l. Debería ser obvio que la especificación anterior garantiza maxCont l = maxCont' 0 0 l, que es lo que queremos. En lugar de tratar de explicar directamente por qué la versión final de maxCont 'implementa la especificación anterior (que realmente no sé cómo hacer), mostraré cómo se puede derivar de ella, transformando la especificación un paso a la vez hasta se convierte en el código, que sin duda será correcto. Tal como está escrito, esta especificación no proporciona una implementación: si se define maxCont en términos de maxCont' como se describió anteriormente, se repetirá para siempre como maxCont' llama a maxCont llama a maxCont' con la misma lista. Así que vamos a ampliar a cabo sólo un poco para exponer las piezas que necesitaremos:

maxCont' maxSum thisSum (x:xs) = 
        maximum [maxSum, thisSum + maxInit (x:xs), maxCont (x:xs)] 

Esto no se soluciona nada todavía, pero expuestos cosas. Usemos eso. thisSum + maxInit (x:xs) es thisSum o thisSum + x + maxInit xs. Pero thisSum ≤ maxSum por la condición previa, por lo que podemos ignorar esta posibilidad al calcular el máximo. maxCont (x:xs) es una suma que incluye x o no. Pero si incluye x, entonces es lo mismo que maxInit (x:xs), que está cubierto por el anterior, por lo que podemos ignorar esa posibilidad, y solo considerar el caso donde maxCont (x:xs) = maxCont xs. Así, llegamos a la siguiente versión:

maxCont' maxSum thisSum (x:xs) = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs] 

Ésta, por último, es propiamente recursiva, pero tenemos mucho camino por recorrer para llegar a un código eficiente, sobre todo debido a que maxInit mítica sería demasiado lento. Vamos a romper hacia abajo en los tres casos considerados en el código Java (abuso de notación Haskell un poco):

maxCont' maxSum thisSum (x:xs) 
    | maxSum < thisSum + x  = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs] 
    | thisSum + x < 0   = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs] 
    | 0 ≤ thisSum + x ≤ maxSum = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs] 

En el primer caso, sabemos que maxSum no puede ser la máxima: thisSum+x es mayor y maxInit xs es siempre positivo. En el segundo caso, sabemos que thisSum+x+maxInit xs no puede ser el máximo: maxCont xs siempre es al menos tan grande como maxInit xs, y thisSum+x es negativo.Así que podemos eliminar esas posibilidades:

maxCont' maxSum thisSum (x:xs) 
    | maxSum < thisSum + x  = maximum [  thisSum+x+maxInit xs, maxCont xs] 
    | thisSum + x < 0   = maximum [maxSum,      maxCont xs] 
    | 0 ≤ thisSum + x ≤ maxSum = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs] 

Ahora tenemos apenas una ventaja suficiente para cambiar las cosas. Ahora que hemos eliminado casos imposibles, vamos a agregar algunos casos duplicados, que colocarán estos tres casos en la misma forma para que podamos sustituirlos por la especificación original maxCont'. En el primer caso, no tenemos un primer término, por lo que debemos usar algo que sabemos que no excederá los otros términos. Para mantener el invariante que thisSum ≤ maxSum, necesitaremos usar thisSum+x. En el segundo caso, no tenemos un segundo término que se parece a something+maxInit xs, pero sabemos que maxInit xs ≤ maxCont xs, por lo que podemos pegar con seguridad en 0+maxInit xs. La incorporación de estos términos adicionales para la regularidad se obtiene la siguiente:

maxCont' maxSum thisSum (x:xs) 
    | maxSum < thisSum + x  = maximum [(thisSum+x), (thisSum+x)+maxInit xs, maxCont xs] 
    | thisSum + x < 0   = maximum [maxSum,  0+maxInit xs,   maxCont xs] 
    | 0 ≤ thisSum + x ≤ maxSum = maximum [maxSum,  thisSum+x+maxInit xs, maxCont xs] 

Por último, después de haber comprobado la condición previa, sustituimos en la especificación,

maxCont' maxSum thisSum l = maximum [maxSum, thisSum + maxInit l, maxCont l] 

para obtener

maxCont' maxSum thisSum (x:xs) 
    | maxSum < thisSum + x  = maxCont' (thisSum+x) (thisSum+x) xs 
    | thisSum + x < 0   = maxCont' maxSum 0 xs 
    | 0 ≤ thisSum + x ≤ maxSum = maxCont' maxSum (thisSum+x) xs 

La fijación de este arriba en la sintaxis real y las tachuelas en el caso base omitido dan como resultado el algoritmo real, que ahora hemos demostrado que cumple con la especificación siempre que termine. Pero cada paso sucesivo recursivo opera en una lista más corta, por lo que de hecho termina.

Sólo hay una última cosa que hacer, por mi causa, que es escribir el código final más idiomáticamente y flexible:

maxCont :: (Num a, Ord a) => [a] -> a 
maxCont = fst . foldl maxCont' (0,0) 
    where 
    maxCont' (maxSum, thisSum) x 
     | maxSum < newSum = (newSum, newSum) 
     | newSum < 0  = (maxSum, 0) 
     | otherwise  = (maxSum, newSum) 
     where newSum = thisSum + x 

Answer 7

he probado esto. En caso de que todos los números sean negativos, devuelve el mayor número negativo.

casos de prueba:

{-5, -1, -2, -3, -4} 
{ 12, 14, 0, -4, 61, -39} 
{2, -8, 3, -2, 4, -10} 

Código:

public int FindLargestSum(int[] arr) 
{ 
    int max = Integer.MIN_VALUE; 
    int sum = 0; 

     for(int i=0; i < arr.length; i++) 
     { 
      if(arr[i] > max) max = arr[i]; 

      sum += arr[i]; 

      if(sum < 0) 
       sum = 0; 
      else if(sum > max) 
       max = sum; 
     } 

    return max; 
}