suma más grande subarreglo contigua (Pregunta De la Entrevista)

Question

Duplicar posibles:
Find the maximum interval sum in a list of real numbers.

me hizo la siguiente pregunta hoy en Adobe entrevista para el puesto de ingeniero de software.

Problema Dada una matriz arr[1..n] de enteros. Escribe un algoritmo para encontrar la suma de submatriz contigua dentro de la matriz que tiene la suma más grande. Devuelve 0 si todos los números son negativos.

Ejemplo

Dada array arr[1..6] = [ 12, 14, 0, -4, 61, -39 ]

respuesta

83 construido con [ 12, 14, 0, -4, 61 ].

Podría encontrar una solución ejecutándose en O(n logn) pero no creo que sea muy eficiente. El entrevistador me pidió que escribiera un algoritmo O(n). No podría venir con eso.

¿Alguna idea sobre cómo escribir una solución O(n) para este problema? Algoritmo a implementar en C/C++/Java.

Gracias de antemano

Answer 1

Puede utilizar Kadane's algorithm que se ejecuta en O (n).

Aquí es el algoritmo (descaradamente copiado de here)

Initialize: 
    max_so_far = 0 
    max_ending_here = 0 

Loop for each element of the array 
    (a) max_ending_here = max_ending_here + a[i] 
    (b) if(max_ending_here < 0) 
      max_ending_here = 0 
    (c) if(max_so_far < max_ending_here) 
      max_so_far = max_ending_here 
return max_so_far