Pagini recente » Cod sursa (job #2258705) | Istoria paginii utilizator/tynman88ro | Cod sursa (job #2532374) | Cod sursa (job #1752678) | Cod sursa (job #447627)
Cod sursa(job #447627)
#include <stdio.h>
#define IN_FILE "secv2.in"
#define OUT_FILE "secv2.out"
#define MAX_N 50000
#define MIN_SUM -1250000001
int N, K;
int numere[MAX_N + 1];
int max(int n1, int n2)
{
return ((n1 > n2) ? n1 : n2);
}
int main(void)
{
int i, j, sum_last_k;
int max_sum, begin, end;
int S[MAX_N + 1], len[MAX_N + 1];
FILE *fin, *fout;
fin = fopen(IN_FILE, "r");
fscanf(fin, "%d %d\n", &N, &K);
for (i = 1; i <= N; i++)
{
fscanf(fin, "%d ", numere+i);
}
fclose(fin);
len[K] = K;
S[K] = 0;
for (i = 1; i <= K; i++)
S[K]+= numere[i];
max_sum = MIN_SUM;
for (i = K + 1; i <= N; i++)
{
if (len[i-1] == K)
{
if ( (S[i-1] + numere[i]) > (S[i-1] + numere[i] - numere[i-K]) )
{
len[i] = K + 1;
S[i] = S[i-1] + numere[i];
}
else
{
len[i] = K;
S[i] = S[i-1] + numere[i] - numere[i-K];
}
}
else
{
if (numere[i - K] < 0)
{
sum_last_k = 0;
for (j = i - K + 1; j <= i; j++)
sum_last_k+= numere[j];
if (sum_last_k > S[i - 1] + numere[i])
{
S[i] = sum_last_k;
len[i] = K;
}
else
{
S[i] = S[i-1] + numere[i];
len[i] = len[i-1] + 1;
}
}
else
{
S[i] = S[i-1] + numere[i]; //aici ar putea fi eliminata un pic redundanta
len[i] = len[i-1] + 1;
}
}
if (S[i] > max_sum)
{
max_sum = S[i];
end = i;
begin = i - len[i] + 1;
}
}
fout = fopen(OUT_FILE, "w");
fprintf(fout, "%d %d %d\n", begin, end, max_sum);
fclose(fout);
return 0;
}