jueves, 11 de noviembre de 2010

Subvector de suma máxima

El problema del subvector de suma máxima trata de encontrar dentro de un vector de longitud n un segmento de longitud m (m<=n) tal que la suma de los elementos de dicho segmento sea máxima. Es decir que no haya otro segmento en el vector donde la suma de sus elementos sea mayor.

La solución que se propone a continuación tiene costo lineal.

#include <stdlib.h>
#include <stdio.h>

int main() {
 int *v, n;
 
 scanf("%d", &n);
 v = new int [n];
 for(int i=0; i<n; i++) {
  scanf("%d", &v[i]);
 }
 
 int a=0, b=0, smax=v[0], sseq=v[0], pos=0;
 for(int i=1; i<n; i++) {
  sseq += v[i];
  if(sseq <= 0) {
   sseq = v[i];
   pos = i;
  }
  if(sseq > smax) {
   smax = sseq;
   a = pos;
   b = i;
  }
 }
 printf("%d %d %d", a, b, smax);
 return 0;
}

Saludos

1 comentario: