sexta-feira, 7 de setembro de 2012

Programação Dinâmica - Algoritmo de Kadane


O problema de segmento de soma máxima é a tarefa de encontrar um subvetor com a maior soma possivel. Por exemplo, para a seguinte sequência de valores -2,1,-3,4,-1,2,1,-5,4; o segmento de soma máxima é 4,-1,2,1 com soma 6. O algoritmo trivial seria esse:

void seg_max(int *v, int n, int & x, int &y , int & max){
 int i,j;
 int soma; 
 max = -1; 
 for(i=0;i<n;i++){
  soma = 0;
  for(j=i;j<n;j++){
   soma += v[j];
   if( soma > max ){
    max = soma;
    x = i;
    y = j;
   }
  }
 }
}

int main(){
int x,y,max;
int v[] = {-2,1,-3,4,-1,2,1,-5,4};
seg_max(v,9,x,y,max);
printf("segmento de soma maxima [%d-%d] com soma %d\n", x,y,max);
}




Saída
segmento de soma maxima [3-6] com soma 6

O algoritmo acima tem complexidade O(n*n). Em 1977, Jay Kadane desenvolveu um algoritmo linear para resolver este problema. A idéia do algoritmo é simples, basta atualizar duas variáveis o max_atual e o max_total; A regra para atualizar o max_atual é:

max_atual = max( max_atual + v[i] , v[i]). 

A regra para atualizar o max_total é:

max_total = max( max_total , max_atual )

A ideia é incrementar o max_atual com o próximo valor da sequência enquanto o valor de max_atual não fica negativo. 


void kadane(int *v, int n, int & x, int &y , int & max_total){
 int max_atual;
 int xtemp;
 int i;
 max_atual = 0;
 max_total = -1;
 xtemp = 0;
 for(i=0;i<n;i++){
  max_atual = max_atual + v[i];
  if(max_atual < 0) { 
   max_atual = 0;
   xtemp = i+1;
  }
  if(max_atual > max_total){
   max_total = max_atual;
   x = xtemp;
   y = i;
  } 
 }
}
int main(){
 int x,y,max;
 int v[] = {-2,1,-3,4,-1,2,1,-5,4};
 kadane(v,9,x,y,max);
 printf("segmento de soma maxima [%d-%d] com soma %d\n", x,y,max);
}

Saída
segmento de soma maxima [3-6] com soma 6


Teste esses algoritmo nos seguintes problemas:
http://br.spoj.pl/problems/BAPOSTAS/ 
http://br.spoj.pl/problems/SALDO/ 








4 comentários:

Bonilha disse...

interessante

Adriano disse...

Muito interessante.

Como ficaria para uma entrada só com números negativos? Eu tentei adaptar mas não obtive êxito.

Leandro de Andrade Moura disse...

Se vc ainda tiver o interesse de descobrir a solução, me procure.

Ricardo Ferreira disse...

Bom dia, boa tarde, boa noite, estou muito feliz porque, como a maioria já sabe sou apaixonado por tecnologia, e não poderia deixar de compartilhar com vocês um curso que tem me ajudado entender mais sobre programação, esse curso é muito barato, por menos de R$100,00 você assim como eu poderá praticar sem muitas dificuldades, caso tenha alguma dificuldade o curso da vários tipos de suportes, espero ter Ajudado
O link do Curso de Algoritmo e Programação é http://goo.gl/4gxc6b
Conheça alguns dos meus trabalhos www.tecnologiateen.com