Pagini recente » Rezultatele filtrării | Cod sursa (job #132458)
Cod sursa(job #132458)
//Subsecventa de suma maxima de lungime >= L, complexitate O(n), varianta 1
#include <stdio.h>
int n, v[50001], max, l;
int main()
{
freopen("secv2.in","r",stdin);
freopen("secv2.out","w",stdout);
int i, sc, pi, pf, p;
scanf("%d %d",&n, &l);
for (i = 1; i <= n; i++) scanf("%d",&v[i]);
p = pi = pf = 1;
sc = max = v[1];
for (i = 2; i <= n; i++)
{
if (sc < 0)
{
sc = v[i];
p = i;
}
else sc += v[i];
if (max < sc && i - p + 1 >= l)
{
max = sc;
pi = p;
pf = i;
}
}
printf("%d %d %d\n", pi, pf, max);
return 0;
}