ALGORITMO DE KADANE
Para hallar la Subsecuencia (o el Subarreglo) de suma mxima
Empezamos con una ejemplificacin del problema: Dada una secuencia
de nmeros enteros V = [ 15, -10, -30, -2, -1, 11, -10, 10, -4, 10, -5, 1 ].
Se trata de hallar la subsecuencia (sin saltos) de mayor suma.
Por ejemplo la subsecuencia 15,11,10,10,1 no nos sirve porque tiene
saltos.
Una subsecuencia lcita pero no de suma mxima es 15.
Otra subsecuencia es 15,-10,-30 cuya suma es -25.
Cuando slo hay negativos la respuesta es una subsecuencia nula cuya
suma es 0.
Hay abundante literatura que muestra algoritmos O(n3) con tres ciclos
que abarcan todas las subsecuenc ias posibles (de tamao 1, de 2, etc.)
Tambin hay diversas versiones de la idea de Kadane.
Aqu mostraremos la que nos parece ms simple.
Obviamente empezamos con un max=0 e iremos actualizando este
mximo.
La idea es ir desde V[1] e ir sumando elemento a elemento.
Si nuestra suma actual es negativa: Empezaremos en el siguiente
elemento con una suma actual iguala 0. Ms adelante probaremos que
no se pierden mximos siguiendo este procedimiento.
En el ejemplo la idea de Kadane sera as:
max0
sumaActual0
Y vamos de elemento en elemento:
sumaActual sumaActual+V[1] (= 0+15 = 15)
como nuestra suma actual es mayor que max
actualizamos ello max15
(que empieza en la posicin 1 y termina en la posicin
1)
sumaActual sumaActual+V[2] (= 15+[-10] = 5)
como nuestra suma actual no es mayor que max no
actualizamos
sumaActual sumaActual+V[3] (= 5+[-30] = -25)
como nuestra suma actual no es mayor que max no
actualizamos
acumulacin
Pero adems y esta es la genialidad de Kadane:
La siguiente sumaActual0 y empezamos la nueva
desde el siguiente elemento en la cuarta posicin
sumaActual sumaActual+V[4] (= 0+[-2] = -2)
como nuestra suma actual no es mayor que max no
actualizamos
Pero adems y empezamos en la siguiente posicin
con sumaActual0
Pasa lo mismo con la quinta posicin, pero las cosas se ponen
interesantes al empezar en la sexta posicin:
sumaActual sumaActual+V[6]
(= 0+11 = 11)
sumaActual sumaActual+V[7]
(= 11+(-10) = 1)
sumaActual sumaActual+V[8]
(= 1+10 = 11)
sumaActual sumaActual+V[9]
(= 11+(-4) = 7)
sumaActual sumaActual+V[10] (= 7+10 = 17)
max17 (empieza en
pos 6 y termina en pos 10)
Etc.
Es obvio que debemos conocer las posiciones donde empiezan y
terminan nuestros sucesivos mximos, ello puede hacerse al actualizar
max como se ve en el siguiente algoritmo.
Entrada: Vector V[1..n]
Salida:
La subsecuencia de suma mxima
max 0
i 1
inic_max, fin_max
null, null
sumaActual 0
For j = 1..n
sumaActual sumaActual + V[j]
If sumaActual > max Then max sumaActual
inic_max i
fin_max
FinIf
If sumaActual < 0 Then
sumaActual 0
i
FinIf
FinFor
j+1
Retornar max, inic_max, fin_max
Ntese que el algoritmo es O(n).
Resta probar que la idea es correcta: que cuando la sumaActual es
negativa podemos empezar en el siguiente elemento y que no
perderemos algn mximo por hacer ello.
Denotaremos por Vi,j a la subsecuencia que empieza en la posicin i y
termina en la posicin j.
Denotaremos por Si,j a la suma de los elementos de Vi,j.
Resultado:
SI Si,j < 0 ENTONCES
Demostracin:
Si,j < 0
j<q Si,q no puede ser mximo.
sumando a ambos lados de la desigualdad
Sj+1,q
Si,j + Sj+1,q < 0 + Sj+1,q
Si,q
< Sj+1,q
como Si,j + Sj+1,q = Si,q
Por lo tanto Si,q no puede ser mximo pues hay otra subsecuencia Vj+1,q
con una suma ms grande.
Esto alivia cualquier preocupacin de alguien que crea que hay una
subsecuencia mxima que empiece antes de que sumaActual sea
negativa (en la posicin i) y que termine ms alla de la posicin donde
sumaActual se hace negativa.
El siguiente resultado terminar de aliviar las preocupaciones de alguien
que crea que hay un mximo que empiece antes de que sumaActual sea
negativa (incluso luego de la posicin i) y que termine ms alla de la
posicin donde sumaActual se hace negativa.
Resultado:
i
Sea j la primera posicin tal que Si,j < 0
ENTONCES p ipj ^ pq
Vp,q no es una subsecuencia mxima
o la suma de sus elementos Sp,q es igual a un mximo
ya calculado
Demostracin:
La dividiremos en dos partes:
i) Cuando qj
El siguiente grfico da una
idea:
Es claro que Si,p-1 + Sp,q = Si,q
Recordemos que j es la primera posicin tal que Si,j < 0.
Como la posicin (p-1) est antes de la posicin j, resulta que hasta (p-1)
la suma (desde i) no se ha hecho negativa. Es decir:
Si,p-1
0
sumando a ambos lados de la desigualdad
SP,q
Si,p-1 + Sp,q 0 + Sp,q
Si,q
Sp,q
que obviamente resulta en
Si Si,q > Sp,q: Obviamente Vp,q no puede ser una subsecuencia mxima
(hay otra subsecuencia -de i hasta q- cuya suma es ms grande).
Si Si,q = Sp,q: La suma desde i hasta q ya ha sido calculada en
sumaActual (que si fue un mxima con seguridad ya ha sido registrada).
ii) Cuando j<q
El resultado anterior se aplica: Si,j < 0, luego cualquier Si,q no puede
ser mximo.
Eso cubre el caso cuando p=i.
Cuando i<p, el siguiente grfico da una idea:
Es claro que Si,p-1 + Sp,q = Si,q
Recordemos que j es la primera posicin tal que Si,j < 0.
Como la posicin (p-1) est antes de la posicin j, resulta que hasta (p1) la suma
(desde i) no se ha hecho negativa. Es decir:
Si,p-1
0
sumando a ambos lados de la desigualdad
SP,q
Si,p-1 + Sp,q 0 + Sp,q
Si,q
Sp,q
que obviamente resulta en
Si Si,q > Sp,q: Obviamente Vp,q no puede ser una subsecuencia mxima
(hay otra subsecuencia -de i hasta q- cuya suma es ms grande).
Si Si,q = Sp,q: La nica posibilidad para esto es que Si,p-1 = 0. Y en ese
caso:
Sp,j
<0
sumando a ambos lados de la desigualdad
Sj+1,q
SP,j + Sj+1,q < 0 + Sj+1,q
como Si,j + Sj+1,q = Si,q
SP,q
< Sj+1,q
Luego, Vp,q no puede ser una subsecuencia mxima (hay otra
subsecuencia -de j+1 hasta q- cuya suma es ms grande).
Comentario adicional (para notar que incluso tericos de talla no ven
algoritmos ms simples; lo que ms que un demrito para ellos es un
aliciente para nosotros):
Bentley comenta que l y Shamos pensaron que un algoritmo O(n log n)
era el mejor posible para este problema. Shamos dio un seminario que
inclua este detalle y al que asisti Kadane. Cuentan que le tom un
minuto a Jay Kadane disear el algoritmo O(n).
Microsoft Windows [Versin 6.2.9200]
(c) 2012 Microsoft Corporation. Todos los derechos reservados.
C:\Users\USUARIO>f:
F:\>cd pro*
F:\programacion>cd uva
F:\programacion\uva>cd 10503
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
1 2 -4 3 1 -3
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
444410
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
444410
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
133344
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
1 1 1 1 -2 -3
F:\programacion\uva\10503>kadane
1 2 -4 3 1 -3
2
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
111100
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
111100
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
111100
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
011100
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
111100
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
444410
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
4 4 4 4 1 -3
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
133344444410
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
133344
444410
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
8
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
4
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
8
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
8
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
8
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
8
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
7
F:\programacion\uva\10503>kadane
6
1 2 -4 3 1 -3
8
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
18
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
18
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
18
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
2
5
5
6
6
6
7
7
12
12
11
11
11
11
11
9
6
6
18
F:\programacion\uva\10503>kadane
2 3 -1 2 -5 2 4 -1 6
33
205
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
2 5 5 6 6 6 7 7 12
12 11 11 11 11 11 9 6 6 18
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
2 5 5 6 6 6 7 7 12
12 11 11 11 11 11 9 6 6
18
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
2 5 5 6 6 6 7 7 12
12 11 11 11 11 11 9 6 6
18
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
2 5 5 6 6 6 7 7 12
12 11 11 11 11 11 9 6 6
18
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
2 5 5 6 6 6 7 7 12
12 11 11 11 11 11 9 6 6
18
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
2 5 5 6 6 6 7 7 12
12 11 11 11 11 11 9 6 6
17
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
17
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
2 5 5 6 6 6 7 7 12 12 11 11 11 11 11 9 6 6 17
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
2 5 5 6 6 6 7 7 12
12 11 11 11 11 11 9 6 6
17
F:\programacion\uva\10503>
18
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
2 5 5 6 6 6 7 7 12
12 11 11 11 11 11 9 6 6
18
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
2 5 5 6 6 6 7 7 12
12 11 11 11 11 11 9 6 6
18
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
2 5 5 6 6 6 7 7 12
12 11 11 11 11 11 9 6 6
18
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
2 5 5 6 6 6 7 7 12
12 11 11 11 11 11 9 6 6
17
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
17
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
2 5 5 6 6 6 7 7 12 12 11 11 11 11 11 9 6 6 17
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
2 5 5 6 6 6 7 7 12
12 11 11 11 11 11 9 6 6
17
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
2 5 5 6 6 6 7 7 12
12 11 11 11 11 11 9 6 6
17
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
2 5 5 6 6 6 7 7 12
12 11 11 11 11 11 9 6 6
17
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
2 5 5 6 6 6 7 7 12
12 11 11 11 11 11 9 6 6
17
F:\programacion\uva\10503>kadane
r5
0
F:\programacion\uva\10503>kadane
1
2
2
2
2
F:\programacion\uva\10503>kadane
3
2
2
2
246
642
6
F:\programacion\uva\10503>kadane
5
1 2 -3 4 5
13349
99995
12
F:\programacion\uva\10503>kadane
5
-2 -2 -2 -2 -2
00000
00000
0
F:\programacion\uva\10503>kadane
5
-2 -2 -2 2
3
00000
55553
5
F:\programacion\uva\10503>kadane
5
-2 4 -5 6 -3
02233
33330
5
F:\programacion\uva\10503>kadane
5
-2 4 -5 6 -3
02233
33330
5
F:\programacion\uva\10503>kadane
5
-2 4 -5 89 -3
0 2 2 86 86
86 86 86 86 0
88
F:\programacion\uva\10503>kadane
9
2 3 -1 2 -5 2 4 -1 6
2 5 5 6 6 6 7 7 12
12 11 11 11 11 11 9 6 6
17
F:\programacion\uva\10503>kadane
5
-2 4 -5 6 -3
04466
33330
7
F:\programacion\uva\10503>kadane
5
-2 4 -5 6 -3
04466
33330
7
F:\programacion\uva\10503>kadane
5
-2 4 -5 6 -3
04466
66660
10
F:\programacion\uva\10503>kadane
5
-2 4 -5 6 -3
10
F:\programacion\uva\10503>kadane
5
1 -32 3 -23
3
6
F:\programacion\uva\10503>kadane
1 -32 3 -23
0
0
0
F:\programacion\uva\10503>kadane
5
1 -32 3 -23
1 -32 3 -23
11333
33311
4
F:\programacion\uva\10503>kadane
4
1 -32 3 -23
1133
3330
4
F:\programacion\uva\10503>kadane
5
1 -32 3 -23
5
11335
55555
8
F:\programacion\uva\10503>kadane
10
17731 -258654 913064 113041 -540997 237433 -380694 -628204
571102 -938674
17731 17731 913064 1026105 1026105 1026105 1026105
1026105 1026105 1026105
1026105 1026105 1026105 571102 571102 571102 571102
571102 571102 0
1597207
F:\programacion\uva\10503>kadane
70
17731
-258654
913064
113041
-540997
237433
-380694
-628204
571102
-938674
731277
470826
461648
53259
427299
941570
-111275
143783
383419
-628339
-773321
516464
228296
-814504
545551
-962245
413699
761886
643802
-928444
679778
-548835
586591
331745
465796
410779
-858561
909485
104617
402608
-509871
-959701
-797925
315271
-85789
-29180
630081
589324
786987
-703035
913858
-524604
557410
891980
-707134
861252
175795
656929
575245
964504
732267
942953
604404
95373
969699
676878
428574
-688680
-184628
-680
17731 17731 913064 1026105 1026105
1026105 1026105 1026105 10261
05 1202103 1663751 1717010 2144309
3118387 3501806 3501806 35018
06 3501806 3501806 3501806 3501806
3501806 3501806 3501806 35018
06 3501806 3501806 3553930 4019726
4481429 4586046 4988654 49886
54 4988654 4988654 4988654 4988654
4988654 4988654 4988654 51386
1026105 1026105
3085879 3085879
3501806 3501806
4430505 4430505
4988654 4988654
74 5138674 5171480 6063460 6063460 6217578 6393373
7050302 7625547 8590051 93223
18 10265271 10869675 10965048 11934747 12611625
13040199 13040199 13040199 13040
199
13040199 13040199 13040199 13040199 13040199 13040199
13040199 13040199 13040199
13040199 13040199 12308922 11838096 11426491 11426491
11426491 11426491 1142649
1 11426491 11426491 11426491 11426491 11426491 11426491
11426491 11426491 114264
91 11012792 10535548 10535548 10535548 10404605
10404605 10319042 10319042 10319
042 10319042 10319042 10319042 10319042 10319042
10319042 10319042 10319042 1011
8740 10118740 10118740 9488659 8899335 8815383 8815383
8426129 8426129 7868719 7
683873 7683873 6822621 6646826 5989897 5414652 4450148
3717881 2774928 2170524 2
075151 1105452 428574 0 0 0
15307696
F:\programacion\uva\10503>
2 1 3 4 5
2 3 6 10 15
15 13 12 9 5
17731-258654+913064
