/* 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);
}