Encontrar la suma más grande de los elementos de una matriz contigua en $\Theta(n) $

Question

Por ejemplo, con la matriz de entrada $[1,3,-5,7,-12,4,-1,5]$ la salida es $8$ $[4,-1,5] $ produce la suma más grande. Creo que la respuesta debe estar en algún tipo de algoritmo de seguimiento hacia atrás, pero no todo él hacia fuera (es decir, que he venido en ninguna parte cerca). He probado tomando los máximos de pares adyacentes, pero el algoritmo resultante no parece trabajar. Simplemente bruta forzar es al menos $\Omega (n^3) $ y no veo las mejoras evidentes de ese algoritmo.

Cualquier ayuda es apreciada.

Answer 1

Deje $a(n)$ denotar la suma de los primeros a $n$ elementos. Desea maximizar $a(i)-a(j)$ donde $i> j$. Mientras computación estas sumas, seguir la pista de la más pequeña que aparece, es decir, vamos a $b(n)=\min\{a(i):i\le n\}$. A continuación, para cada una de las $a(n)$ calcular, calcular $$d(n)=a(n)-b(n-1)$$ y almacenar el máximo de este valor. Cuando llegue al final de la matriz de este valor será su max. Es decir, si $S$ es el max y la matriz es de tamaño $m$, $$S=\max\{d(n): 1<n\le m\}$$ Claramente que sólo el bucle a través de la matriz una vez y sólo necesita almacenar tres variables. Yo la tome de los detalles puede ser llenado en caso necesario (estoy escribiendo en mi teléfono así que estoy teniendo es corto).