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

#define SCALE 3000
int maxnum(int a, int b);
int main(int argc, char const *argv[])
{
 FILE *fp;
 fp = fopen("maximum.in", "r");
 // int x[] = {1,12,-11,10,-65,54,22,-9,21,5,48,5,-8,-2,56,54,-88,-5,2,-8,554,-56,35,-55,555,-65,-545,-23,48,-5,88,-56,16,-8};
 int *x = (int *)malloc(sizeof(int)*(SCALE+1));
 int xi = SCALE,a = 0,num_in = 0;
 while(xi--){
  fscanf(fp, "%d", &x[a++]);
 }
 clock_t start, end;

 // ***Algorithm-1 cube***
 start = clock();

 int max = 0;
 int length = SCALE;
 int i,j,k;
 for (i = 0; i < length; ++i)
 {
  for (j = i; j < length; ++j)
  {
   int sum = 0;
   for (k = i; k <= j; ++k)
   {
    sum += x[k];
   }
   max = maxnum(max, sum);
  }
 }
 
 // long num = 10000000L;
 // while(num--);

 end = clock();
 double times = (double)(end - start)/CLOCKS_PER_SEC;
 double dend = (double)end;
 printf("\n***Algorithm-1 cube***\n");
 printf("end: %f\n", dend);
 printf("Time consuming: %f\n", times);
 printf("%d\n", max);
 // ***Algorithm-2 square***
 start = clock();
 max = 0;
 for (i = 0; i < length; ++i)
 {
  int sum = 0;
  for (j = i; j < length; ++j)
  {
   sum += x[j];
   max = maxnum(max, sum);
  }
 }
 end = clock();
 times = (double)(end - start)/CLOCKS_PER_SEC;
 dend = (double)end;
 printf("\n***Algorithm-2 square***\n");
 printf("end: %f\n", dend);
 printf("Time consuming: %f\n", times);
 printf("%d\n", max);
 // ***Algorithm-3 linear***
 start = clock();
 max = 0;
 int max_end_here = 0;

 for (i = 0; i < length; ++i)
 {
  max_end_here = maxnum(max_end_here + x[i], 0);
  max = maxnum(max, max_end_here);
 }
 end = clock();
 times = (double)(end - start)/CLOCKS_PER_SEC;
 dend = (double)end;
 printf("\n***Algorithm-3 linear***\n");
 printf("end: %f\n", dend);
 printf("Time consuming: %f\n", times);
 printf("%d\n", max);
 free(x);
 x = NULL;
 return 0;
}
int maxnum(int a, int b)
{
 return a > b ? a : b;
}