Programação Dinâmica - Algoritmo de Kadane 2D

Um extensão interessante do problema de encontrar um segmento de soma máxima em um vetor é encontrar uma submatriz de soma máxima em uma matriz a. O algoritmo mais ou menos trivial para esse problema seria O($n^4$).  Primeiramente, vamos construir uma matriz temporária temp.

temp[i][j] = $\sum a[k][l]$ , 1<=k<=i e 1<=l<=j

Podemos calcular temp de uma maneira inteligente fazendo as seguintes observações:

Usando o principio da inclusão-exclusão, temos o seguinte:

$temp[i,j] = temp[i-1,j] + temp[i,j-1] - temp[i-1,j-1] + a[i,j]$

Com a tabela temp calculada, podemos encontrar a soma de uma submatriz que está em cinza rapidamente da seguinte maneira:

$soma = temp[k,l] - temp[k,j-1] - temp[i-1,l] + temp[i-1,j-1]$

Considere a seguinte matriz a:

1	2	-1
-3	-1	4
1	-5	2

A matriz temp calculada seria:

0	0	0	0
0	1	3	2
0	-2	-1	2
0	-1	-5	0

O algoritmo trivial consiste em variar todas as possibilidade i,j,k e l.

void seg_max2d( int **a, int n,int m, int & x1,int & y1 , int & x2, int & y2, int & max){
 int i,j,k,l;
 int temp[n+1][m+1];
 int soma;
 
 for(i=0;i<=n;i++) temp[i][0] = 0;
 for(j=0;j<=m;j++) temp[0][j] = 0;
 
 for(i=1;i<=n;i++)
  for(j=1;j<=m;j++)
   temp[i][j] = temp[i-1][j] + temp[i][j-1] - temp[i-1][j-1] + a[i-1][j-1];
 
 max = -1;   
 for(i=1;i<=n;i++)
  for(j=1;j<=m;j++)
   for(k=i;k<=n;k++)
    for(l=j;l<=m;l++){
     soma = temp[k][l] - temp[i-1][l] - temp[k][j-1] + temp[i-1][j-1];
     if(soma > max){
      max = soma; 
      x1 = i;
      y1 = j;
      x2 = k;
      y2 = l;
     }
    }   
}

No exemplo acima, a soma máxima é 6 e a submatriz é a[2..3,3..3].

A complexidade desse algoritmo é O($n^4$). Podemos aplicar o algoritmo de kadane1D para reduzir a complexidade do algoritmo para O($n^3$).

A idéia do algoritmo kadane2D é aplicar o algoritmo de kadane1D nos seguintes vetores:


Considere a seguinte matriz a:

1	2	-1
-3	-1	4
1	-5	2

1° vetor = 1° linha
1 2 -1 = segmento de soma máxima [1 2]  soma 3
2° vetor = 1° linha + 2° linha
-2 1 3 = segmento de soma máxima [1 3] soma 4
3° vetor = 1° linha + 2° linha + 3° linha
1 -4 5 = segmento de soma máxima [5] soma 5
4° vetor = 2° linha
-3 -1 4 = segmento de soma máxima [4] soma 4
5° vetor = 2° linha + 3° linha
2 -6 6  = segmento de soma máxima [6] soma 6
6° vetor = ° linha
1 -5 2 = segmento de soma máxima [2] soma 2

void kadane2d( int **a, int n,int m, int & x1,int & y1 , int & x2, int & y2, int & max_sum){
  
   int i,j,k;
   int tmp[m];
   int fy1,fy2;
   int cur;
   
   for (i=0; i< n; i++)
   {
       for(k=0; k<m; k++)
           tmp[k] = 0;

       for (j=i; j<n; j++)
       {
           for(k=0; k<m; k++)
               tmp[k] += a[j][k];
           
           kadane(tmp, m, fy1, fy2, cur);

           if (cur > max_sum)
           {
               y1 = fy1;
               y2 = fy2;
               x1 = i;
               x2 = j;
               max_sum = cur;
           }
       }
   } 

}