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

void algoritmoCubico(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+v[j];
			if (soma>somaMaxima) somaMaxima=soma;
		}
		if (soma>somaMaxima) somaMaxima=soma;
		}
	}
	
	FILE * saidaCubica;
	fopen(saidaCubica,"w");
	fprintf(saidaCubica,"%d %f",somaMaxima,tempo);
	fclose(saidaCubica);
	
}

void algoritmoQuadratico(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;
		}
	}
	
	FILE * saidaQuadratica;
	fopen(saidaQuadratica,"w");
	fprintf(saidaQuadratica,"%d %f",somaMaxima,tempo);
	fclose(saidaQuadratica);

}

void algoritmoLinear(int vetor[],int n){
	int somaSufixo,somaMaxima,i,j;
	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;
	}
	
	FILE * saidaLinear;
	fopen(saidaLinear,"w");
	fprintf(saidaLinear,"%d %f",somaMaxima,tempo);
	fclose(saidaLinear);

}

int main(void) {
	
	int qtd, i;
	
	printf ("\n::: Menu de Iteracoes :::\n");
	do { 
		printf ("Digite a quantidade de iteracoes desejadas (zero para sair): ");
		scanf("%d",&qtd);
		
		if (!qtd) { printf("Erro - Este algoritmo nao se aplica a sequencias vazias.\n"); }
		else {
			FILE * entrada;
			
			entrada = fopen("in50000.txt","r");
			int * dados;
			dados = malloc(sizeof(int) * qtd);
			for (i = 0; (i < qtd) && (fscanf(entrada,"%d",&dados[i]) != EOF); i++);
			
			algoritmoLinear(dados, i);
			algoritmoQuadratico(dados, i);
			algoritmoCubico(dados, i);
		}
	}
	while (qtd);
	
	return 0;
}