#include<time.h>
#include<math.h>
#include<iostream>

using namespace std;
/////////////////////////////////////////////////////////////
///////first algorithm
int max_sum_seq_1(int a[],int n,int& low,int& high)
{
	int sum,max=0;
	for(int i=0;i<n;i++)
	for(int j=i;j<n;j++)
	{
		sum=0;
		for(int k=i;k<=j;k++)sum+=a[k];
		{
			if(sum>max){max=sum;low=i;high=j;}
		}
	}
	return max;
}
/////////////////////////////////////////////////////////////
//////Second algorithm
int max_sum_seq_2(int a[],int n,int& low,int& high)
{
	int sum,max=0;
	for(int i=0;i<n;i++)
	{
		sum=0;
		for(int j=i;j<n;j++)
		{
			sum+=a[j];
			if(sum>max){max=sum;high=j;low=i;}
		}
	}
	return max;
}
//////////////////////////////////////////////////////////////
//////Divide and Conquer
int Max_left_edge(int a[],int n,int left,int& right,int arrhigh)
{
	int Sum=0,Max_Sum=0;//right=left-1;
	for(int i=left;i<=arrhigh;i++)
	{
		Sum+=a[i];
		if(Sum >Max_Sum){Max_Sum=Sum;right=i;}
	}
	return Max_Sum;
}
int Max_right_edge(int a[],int n,int& left,int right,int arrlow)
{
	int Sum=0,Max_Sum=0;//left=right+1;
	for(int i=right;i>=arrlow;i--)
	{
		Sum+=a[i];
		if(Sum>=Max_Sum){Max_Sum=Sum;left=i;}
	}
	return Max_Sum;
}
int Max_Middle(int a[],int n,int center,int& low,int& high,int arrlow,int arrhigh)
{

	return Max_right_edge(a,n,low,center,arrlow)+Max_left_edge(a,n,center+1,high,arrhigh);
}

int Max_Seq(int a[],int n,int arrlow,int arrhigh,int& low,int& high)
{
	int max=0,a1,a2,a3,b1,b2,b3,c1,c2,c3;
	if(arrlow==arrhigh)
	{
		if(a[arrlow]>0){high=arrlow;low=arrlow;return a[arrlow];}
		if(a[arrlow]<0){high=-1;low=-1;return -999999;}
	}
	else
	{
		int center=(arrlow+arrhigh)/2;

		a1=Max_Seq(a,n,arrlow,center,a2,a3);
		b1=Max_Seq(a,n,center+1,arrhigh,b2,b3);
		c1=Max_Middle(a,n,center,c2,c3,arrlow,arrhigh);
		if(a1>max){max=a1;low=a2;high=a3;}
		if(b1>max){max=b1;low=b2;high=b3;}
		if(c1>max){max=c1;low=c2;high=c3;}
		return max;
	}
	return -1;
}
int max_sum_seq_3(int a[],int n,int& low,int& high)
{  
	return Max_Seq(a,n,0,n-1,low,high);
}
////////////////////////////////////////////////////////////////
///////Best algorithm
int  max_sum_seq_4(int a[],int n,int& low,int& high)
{
	int max=0,sum=0,midlow=0;
	for(int i=0;i<n;i++)
	{
		sum+=a[i];
		if(sum>max){max=sum;high=i,low=midlow;}
		if(sum<0){sum=0;midlow=i+1;}
	}
	return max;
}
///////////////////////////////////////////////////////////////


int main()
{
	srand(time(NULL));
	clock_t start,finish;		
	int time=1/CLOCKS_PER_SEC;

	int n[13]={10,20,50,100,200,500,1000,2000,5000,10000,20000,50000,100000};
	int a1,a2;
	int result[4][13][11];////first[]stand for 0,...3 algorithms;
	                 ////second[]stand for 0,...12 n of numbers;
	                 ////third[]0,...9 10 times clockcycle;
	                 /////sum stored in result[][][10];

	int a[100000];
	for(int i=0;i<13;i++)////////each value of n[13];
	{
		for(int t=0;t<4;t++)
			result[t][i][10]=0;
		for(int k=0;k<10;k++)//////make 10 runs;
		{
			for(int j=0;j<n[i];j++)///////generate n[i] random numbers;
				a[j]=rand()%100-50;

            start=clock();
			cout<<
			max_sum_seq_1(a,n[i],a1,a2);
			cout<<" "<<a1<<" "<<a2<<endl;
            finish=clock();
			result[0][i][k]=(finish-start);
			result[0][i][10]+=result[0][i][k];


			start=clock();
			cout<<
			max_sum_seq_2(a,n[i],a1,a2);
			cout<<" "<<a1<<" "<<a2<<endl;
            finish=clock();
			result[1][i][k]=(finish-start);
			result[1][i][10]+=result[1][i][k];

 
			start=clock();
			cout<<
			max_sum_seq_3(a,n[i],a1,a2);
			cout<<" "<<a1<<" "<<a2<<endl;
            finish=clock();
			result[2][i][k]=(finish-start);
			result[2][i][10]+=result[2][i][k];

 
			start=clock();
			cout<<
			max_sum_seq_4(a,n[i],a1,a2);
			cout<<" "<<a1<<" "<<a2<<endl;
            finish=clock();
			result[3][i][k]=(finish-start);
			result[3][i][10]+=result[3][i][k];
		}
	}
	for(i=0;i<13;i++)
	{
		for(int j=0;j<4;j++)
	 	cout<<result[j][i][10]<<" ";
		cout<<endl;
	}


	return 0;
}