/* vectmsum.c Dado um vetor com nĂºmeros positivos e negativos aleatoriamente distribuidos, obtenha um subvetor de elementos consecutivos cuja soma seja maxima - MC404B - Out 2001 */ #include <stdlib.h> #define TMAX 16 #define RANGE 128 void rand8(char tab[], unsigned int size) /* generate random integers between -RANGE,+RANGE */ { unsigned int i; int sum; srand(time()); /*comment this line to always get the same sequence */ printf("\nGenerating %d random signed integers:\n",size); for (i=0; i<size; i++){ sum= rand()%(2*RANGE); tab[i]= (sum <RANGE)?sum:RANGE-sum -1; printf("%4d,",tab[i]); } } int main() { int i,j,start,end,csum,maxsum; char tab[TMAX]; rand8(tab,TMAX); /*initialize vector with randomn signed 8 bit integers*/ csum=maxsum=start=0; end=-1; for (i=0, j=0; j < TMAX; j++){ csum= csum + tab[j]; if (csum> maxsum){ maxsum=csum; start= i; end=j; }else if (csum < 0){ i= j+1; csum=0; } } printf("\nsubvector with largest sum:\n start end sum\n"); printf("%6d %6d %6d\n",start,end,maxsum); }