#include <stdlib.h>
#include <stdio.h>
#include <time.h>
//Função que calcula a maior subsequencia usando um algoritmo de complexidade quadrática
int quadratico(int vetor[],int n){
	int soma,somaMaxima,i,j;
	somaMaxima=0;
	for (i=0;i<n;i++){
		soma=0;
		for (j=i;j<n;j++){
			soma=soma+vetor[j];
			if (soma>somaMaxima) somaMaxima=soma;
		}
	}
	return somaMaxima;
}	
//Função que calcula a maior subsequencia usando um algoritmo de complexidade linear
int linear(int vetor[],int n){
	int somaSufixo,somaMaxima,i;
	somaMaxima=0;
	somaSufixo=0;
	for (i=0;i<n;i++){
		if ((vetor[i]+somaSufixo)>somaMaxima){
			somaSufixo=vetor[i]+somaSufixo;
			somaMaxima=somaSufixo;
		}
		else
			if ((vetor[i]+somaSufixo)>0)
				somaSufixo=vetor[i]+somaSufixo;
			else 
				somaSufixo=0;
	}
	return somaMaxima;
}
//Função que calcula a maior subsequencia usando um algoritmo de complexidade cubica
int cubico(int vetor[],int n){
	int soma,somaMaxima,i,j,k;
	somaMaxima=0;
	for (i=0;i<n;i++){
		for (j=i;j<n;j++){
			soma=0;
			for (k=i;k<j+1;k++)
				soma=soma+vetor[k];
            if (soma>somaMaxima) somaMaxima=soma;             
		}
	}
	return somaMaxima;
}		
//Funcao principal
int main(int argc,char *argv[]){
	//Verifica se o numero de argumentos de entrada está correto
	if (argc != 2){
		printf("Erro, digite tambem o nome do arquivo a ser lido\n");
		exit(0);
	}
	printf("\nPrograma para trabalhar com diversas complexidades de algoritmos\n");
	printf("da maior soma subsequente\n");
	//Variavel que guarda o calculo do tempo de execucao
	float tempo;
	//Variaveis para armazenar o tempo inicial e final dado em ciclos de clock
	clock_t t1,t2;
	//A variável opcao armazena a opcao digitada pelo usuario, a variavel i para o laco,n armazena o numero de dados a ser trabalhado
	int opcao,n,i;
	//Ponteiro (vetor a ser alocado dinamicamente mais a frente) que armazena os numeros do arquivo fornecido
	int *vetor;
	//Arquivos de entrada e saida
	FILE *entrada,*saida;
	//Laco enquanto o usuario nao digitar 0
	do{
		printf("\n-------Menu de opcoes--------\n");
		printf("1-Algoritmo linear\n");
		printf("2-Algoritmo quadratico\n");
		printf("3-ALgoritmo cubico\n");
		printf("0-Para sair\n>>");
		scanf("%d",&opcao);
		switch(opcao){
			case 1:
                 //Abre o arquivo para saida
				saida=fopen("linear.txt","w");
				for (n=0;n<50001;n=n+5000){
					//Abre o arquivo de entrada
					if (!(entrada=fopen(argv[1],"r"))){
						printf("Falha na abertura do arquivo 	%s\n",argv[1]);
						exit(0);
					}
					//Aloca dinamicamente espaco para o vetor
					vetor=(int*)malloc(sizeof(int)*n);
					//lê do arquivo e armazena no vetor
					for(i=0;i<n;i++)
						fscanf(entrada,"%d",&vetor[i]);
					//Fecha o arquivo
					fclose(entrada);
					//Armazena o tempo inicial em ciclos de clock
					t1=clock();
					//Chama a funcao que calcula a maior subsequencia
					linear(vetor,n);
					//Armazena o tempo final
					t2=clock();
					//Calcula o tempo em segundos
					tempo=(float)(t2-t1)/CLOCKS_PER_SEC;
					//Escreve na tela o tempo de execucao
					printf("\nO tempo de execucao com %d valores: %f s. \n",n,tempo);
					//Guarda no arquivo o numero de dados trabalhados e o tempo de execucao com o algoritmo
					fprintf(saida,"%d\t%f\n",n,tempo);
					//Libera o espaco alocado anteriormente
					free(vetor);
				}
				//Fecha o arquivo de saida
				fclose(saida);
				printf("\nArquivo linear.txt gerado com os valores calculados\n");
				break;
			case 2:
                   //Abre o arquivo para saida
				saida=fopen("quadratico.txt","w");
				for (n=0;n<50001;n=n+5000){
					//Abre o arquivo de entrada
					if (!(entrada=fopen(argv[1],"r"))){
						printf("Falha na abertura do arquivo 	%s\n",argv[1]);
						exit(0);
					}
					//Aloca dinamicamente espaco para o vetor
					vetor=(int*)malloc(sizeof(int)*n);
					//lê do arquivo e armazena no vetor
					for(i=0;i<n;i++)
						fscanf(entrada,"%d",&vetor[i]);
					//Fecha o arquivo
					fclose(entrada);
					//Armazena o tempo inicial em ciclos de clock
					t1=clock();
					//Chama a funcao que calcula a maior subsequencia
					quadratico(vetor,n);
					//Armazena o tempo final em ciclos de clock
					t2=clock();
					//Calcula o tempo em segundos
					tempo=(float)(t2-t1)/CLOCKS_PER_SEC;
					//Guarda no arquivo
					fprintf(saida,"%d\t%f\n",n,tempo);
					//Imprime na tela o numero de dados trablhados e o tempo de execucao
					printf("\nO tempo de execucao com %d valores: %f s. \n",n,tempo);
					//Libera o espaco alocado anteriormente
					free(vetor);
				}
				//Fecha o arquivo de saida
				fclose(saida);
				printf("\nArquivo quadratico.txt gerado com os valores calculados\n");
				break;
			case 3:
				//Abre o arquivo de saida
				saida=fopen("cubico.txt","w");
				for (n=0;n<2300;n=n+100){
					//Abre o arquivo de entrada
					if (!(entrada=fopen(argv[1],"r"))){
						printf("Falha na abertura do arquivo 	%s\n",argv[1]);
						exit(0);
					}
					//Aloca dinamicamente espaco para o vetor
					vetor=(int*)malloc(sizeof(int)*n);
					//lê do arquivo e armazena no vetor
					for(i=0;i<n;i++)
						fscanf(entrada,"%d",&vetor[i]);
					//Fecha o arquivo
					fclose(entrada);
					//Armazena o tempo
					t1=clock();
					//Chama a funcao para calcular a maior subsequencia
					cubico(vetor,n);
					//Armazena o tempo final
					t2=clock();
					//Calcula o tempo em segundos
					tempo=(float)(t2-t1)/CLOCKS_PER_SEC;
					printf("\nO tempo de execucao com %d valores: %f s. \n",n,tempo);
					//Guarda no arquivo
					fprintf(saida,"%d\t%f\n",n,tempo);
					//Libera o espaco alocado anteriormente
					free(vetor);
				}
				//Fecha o arquivo de saida
				fclose(saida);
				printf("\nArquivo cubico.txt gerado com os valores calculados\n");
				break;
		}
	}while(opcao>0);
	return 0;
	//Fim do programa
}