// Foroni Marco, vr090274

#include <stdio.h>
#include <stdlib.h>
#define MAX_INT 1000000

void Display_Array(int *, int);
void Interval_Sum(int *, int, int);
int Find_Max(int *, int);

int main()
{
	int *read_inp = (int *)malloc(sizeof(int) * MAX_INT);
	FILE *pf;
	pf = fopen("input.txt","r");
	int count = 0;
	if (pf)
	{
		while(!feof(pf) && count < MAX_INT)
		{
			fscanf(pf, "%d \t", &read_inp[count]);
			count++;
		}
	}
	else
	{
		printf("Errore durante l'apertura del file.\n");
		return (-1);
	}
	int n = read_inp[0];
	int k = read_inp[1];
	int *seq = (int *)malloc(sizeof(int) * n);
	int i;
	for (i = 0; i < n; i++)
		seq[i] = read_inp[2+i];
	printf("La sequenza di %d interi in input è: \n", n);
	Display_Array(seq, n);
	Interval_Sum(seq, n, k);

	free(read_inp);
	return 0;
}

void Display_Array(int *A, int n)
{
	int i;
	for (i = 0; i < n; i++)
		printf("%d ", A[i]);
	printf("\n");
}

void Interval_Sum(int *v, int n, int k)
{
	int *somme = (int *)malloc(sizeof(int) * (n-k+1));
	int j; 
	int *iniz = (int *)malloc(sizeof(int) * (n-k+1));
	int *fin = (int *)malloc(sizeof(int) * (n-k+1));
/*
	// Inizializza somme a 0
	for (j = 0; j < n-k+1; j++)
		somme[j] = 0;
	for (iniz = 0; iniz < n-k+1; iniz++)
		for (j = iniz; j < iniz+k; j++)
			somme[iniz] = somme[iniz] + v[j];
	Display_Array(somme, n-k+1);
*/
	int *csom = (int *)malloc(sizeof(int) * (n-k+1)); // somme complete fino in fondo
	for (j = 0; j < n-k+1; j++)
	{
		iniz[j] = j;
		fin[j] = n-1;//fin[j] = j+k-1;
		csom[j] = 0;
	}
	//Display_Array(iniz, n-k+1);
	//Display_Array(fin, n-k+1);
	int i;
	for (i = 0; i < n-k+1; i++)
		for (j = i; j < n; j++)
			csom[i] = csom[i] + v[j];
	//Display_Array(csom, n-k+1);
	
	int pos_som = 0, neg_som = 0;
	for (i = 0; i < n-k+1; i++)
	{	
		int last = n-1; //printf("last = %d\n", last);
		while(last >= iniz[i] + k) // ??? >= OK
		{
			if (v[last] < 0)
			{
				csom[i] = csom[i] - v[last];
				fin[i]--;
				last--;
			}
			else
			{
				while(v[last] > 0 & last >= iniz[i] + k) // ??? >= OK
				{
					pos_som = pos_som + v[last];
					last--;
				}
				while(v[last] < 0 & last >= iniz[i] + k) // ??? >= OK
				{
					neg_som = neg_som + v[last];
					last--;
				}
				if (last >= iniz[i] + k)
				{
					if (abs(pos_som) < abs(neg_som))
					{
						csom[i] = csom[i] - pos_som + abs(neg_som); // ??? OK
						fin[i] = last;
					}
				}
			}
		}
	}
	printf("\n");
	Display_Array(csom, n-k+1);
	int pos_max = Find_Max(csom, n-k+1);	
	printf("\nIl valore massimo della somma di almeno k=%d interi consecutivi nella sequenza in input è: %d.\n", k, csom[pos_max]);
	printf("Corrisponde alla somma degli interi dalla posizione %d alla posizione %d.(Partendo da 0).\n", iniz[pos_max], fin[pos_max]);
	printf("\nIndici finali: ");	
	Display_Array(fin, n-k+1);

	FILE *pf;
	pf = fopen("output.txt", "w");
	if (pf)
	{
		fprintf(pf, "%d", csom[pos_max]);
	}
	else
	{
		printf("Errore durante l'apertura del file output.txt.\n");
	}	
}

int Find_Max(int *v, int n)
{
	int max = v[0];
	int pos_max = 0;
	int i;
	for (i = 0; i < n; i++)
	{
		if (v[i] > max)
		{
			max = v[i];
			pos_max = i;
		}
	}	
	return pos_max;
}