Cómo encontrar un segmento en una matriz con un número máximo de elementos con suma S

¿Qué se almacena en los elementos de la matriz? Suponiendo números reales.

Deje que la matriz A tenga n elementos. Tendrá n segmentos de longitud 1, n-1 segmentos de longitud 2, n-3 segmentos de longitud 3, … 1 segmento de longitud n; para un total de:

[matemática] n + n-1 + n-2 +… + 1 [/ matemática] segmentos

[math] = \ frac {n * (n + 1)} {2} [/ math] segmentos

El método de fuerza bruta para encontrar la suma de cada segmento costará:

una ranura para cada uno de los ~ n ^ 2/2 segmentos y n * 1 + (n-1) 2 + (n-3) 3 +… 1 * n tiempo

[matemáticas] = \ displaystyle \ sum_ {k = 1} ^ {n} (nk-1) (k) = \ displaystyle \ sum_ {k = 1} ^ {n} nk-k ^ 2-k = \ displaystyle \ sum_ {k = 1} ^ {n} (n-1) k – k ^ 2 = \ boxed {\ frac {(n-1) * n * (n + 1)} {2} – \ frac {n ( n + 1) (n + 0.5)} {3}} [/ matemáticas]

[matemáticas] \ aprox \ frac {n ^ 3} {2} – \ frac {n ^ 3} {3} = \ boxed {\ boxed {\ frac {n ^ 3} {6}}} [/ math]

El método de fuerza bruta tendrá una complejidad espacial de [matemática] \ matemática {O} (n ^ 2) [/ matemática] y complejidad temporal de [matemática] \ matemática {O} (n ^ 3) [/ matemática].

Algo

Al almacenar los mismos datos, calculemos las sumas de cada segmento un poco más juiciosamente: primero podemos calcular la suma de cada uno de los segmentos de longitud 1 para que sea el valor del elemento individual. Luego podríamos calcular las sumas de segmentos de longitud dos sumando la suma de vecinos. Los ahorros entran en acción desde segmentos de longitud 3 y superiores, cuando agregamos un elemento al segmento adyacente de la iteración anterior. Ahora la complejidad del tiempo se reducirá a [math] \ mathcal {O} (n ^ 2) [/ math].

Si las matrices almacenan solo + cinco números, como optimización, podemos dejar de construir segmentos más grandes a partir de cualquier segmento que haya alcanzado o excedido S en la generación anterior.

Una vez hecho esto, podemos encontrar los segmentos más grandes con suma S con un recorrido [math] \ mathcal {O} (n ^ 2) [/ math] a través de la matriz de suma.

Este método tendrá una complejidad espacial de [matemática] \ matemática {O} (n ^ 2) [/ matemática] y complejidad temporal de [matemática] \ matemática {O} (n ^ 2) [/ matemática]