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/