constintn=1000;//tamaño del vector (0..n-1)typedefintTvector[n];//estructura del vectorstructvector{intini;intfin;intsuma;};
vectorsubvector_optimo(Tvectorv,intlon,intc,intf){//Variables localesvectorizq,der,cent;//Se divide el vector en tres subvectoresvectoroptimo;//valor devuelto por el metodointm,i;intsuma=0;inttamanio_izq,tamanio_der;/*tamaños del subvector izquierdo y derecho respectivamente*/if(f-c+1<=lon){/*Se comprueba si el vector tiene mayor longitud que el subvector que se esta buscando si la longitud del vector es menor que la del subvector entonces se suman todas las posiciones hasta el final del vector*/for(i=c;i<=f;i++){//coste linealsuma=suma+v[i];};optimo.ini=c;/*operaciones con coste cte*/optimo.fin=f;optimo.suma=suma;}else{/*el vector tiene mayor longitud que la solicitada*/m=(c+f)/2;/*Se halla el punto medio del vector (coste cte)*/izq=subvector_optimo(v,lon,c,m);//coste T(n/2)/*si el vector izquierdo es de menor longitud que "lon" entonces se amplia por la derecha hasta llegar a la longitud "lon" pasada por parametro*/tamanio_izq=izq.fin-izq.ini+1;if(tamanio_izq<lon){while(tamanio_izq<lon){izq.fin++;izq.suma+=v[izq.fin];tamanio_izq++;}}der=subvector_optimo(v,lon,m+1,f);//coste T(n/2)/*si el vector derecho es de menor longitud que "lon" entonces se amplia por la izquierda hasta llegar a la longitud "lon" pasada por parametro*/tamanio_der=der.fin-der.ini+1;if(tamanio_der<lon){while(tamanio_der<lon){der.ini--;der.suma+=v[der.ini];tamanio_der++;}}cent=subvector_central(v,lon,c,f);/*Se calcula cual de los tres subvectores tiene mayor suma*//*Todas las operaciones son de coste cte*/if(izq.suma>=der.suma){if(izq.suma>=cent.suma)optimo=izq;elseoptimo=cent;}elseif(der.suma>=cent.suma)optimo=der;elseoptimo=cent;};returnoptimo;};//fin subvector_optimo
vectorsubvector_central(Tvectorv,intlon,intc,intf){//variables localesintm,suma,suma_max;intinicio,final;/*variables que indican el inicio y el final del subvector pasando por el centro*/vectoroptimo;/*valor devuelto por el metodo*/m=(c+f)/2;//Se calcula el punto medio del vectorsuma_max=INT_MIN;/*Se le asigna el minimo valor de los enteros para poder hacer las comparaciones con "suma", ya que los elementos del vector no valdran nunca el minimo el valor entero*/suma=0;inicio=m-lon+1;final=m+lon-1;/*operaciones con coste cte*/if(inicio<0){inicio=0;/*Se inicializa a cero para que no busque en posiciones inexistentes en el vector*/};if(final>n-1){/*Si se le pasamos una longitud "lon" mas grande que la mitad del vector,tomando como posicion de inicio "m" nos pasaremos del rango del vector original. De ahi la asignacion "final = m+lon- 1" que nos da el limite hasta donde podriamos calcular un subvector de longitud "lon" con inicio en el punto medio "m". Si "final" se pasa del rango solo podremos calcular n-lon+1 subvectores de longitud "lon", o lo que es lo mismo, solo podremos calcular subvectores con inicio entre 0 y n-lon.*//*Calculamos el subvector maximo de forma iterativa*/for(inti=inicio;i<=n-lon;i++){//se hara n-lon-inicio+1 vecessuma=0;for(intj=0;j<lon;j++){//se hara lon vecessuma=suma+v[j+i];};if(suma>=suma_max){suma_max=suma;optimo.suma=suma_max;/*operaciones con coste cte*/optimo.ini=i;optimo.fin=optimo.ini+lon-1;};};}else{/* "final" cae dentro del rango del vector y por tanto se pueden calcular todos los posibles subvectores de longitud "lon" que pasen por el centro (m), incluidos los que tienen como inicio la mitad del vector (m).*//*igual que en el otro caso, se calcula el subvector maximo de forma iterativa*/for(inti=inicio;i<=m;i++){//se hara m-inicio+1 vecessuma=0;for(intj=0;j<lon;j++){//se hara lon vecessuma=suma+v[j+i];};if(suma>=suma_max){suma_max=suma;optimo.suma=suma_max;/*operaciones con coste cte*/optimo.ini=i;optimo.fin=optimo.ini+lon-1;};};};returnoptimo;}//fin subvector_central