Pagini recente » Cod sursa (job #1165231) | Cod sursa (job #1622204) | Cod sursa (job #2138174) | Cod sursa (job #2816947) | Cod sursa (job #383960)
Cod sursa(job #383960)
#include<stdio.h>
#define infile "secv2.in"
#define outfile "secv2.out"
#define nmax (50*1001)
#define inf (~(1<<31))
int a[nmax]; //vectorul a
int b[nmax]; //b[i] = valoarea subsecventei maxime ce se termina in i
int c[nmax]; //c[i] = pozitia de inceput a subsecventei ce se termina in i
int n; //lungimea secventei
int k; //lungimea minima a unei subsecvente
int smax=-inf,st,dr; //suma maxima, repsectiv capetele secventei
void read()
{
int i;
scanf("%d %d\n",&n,&k);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
}
void init()
{
int i;
//initial presupunem ca toate subsecventele au un singur element
for(i=1;i<=n;i++)
b[i]=a[i],c[i]=i;
//acum facem pentru oricate elemente
for(i=2;i<=n;i++)
if(b[i-1] + a[i] > b[i])
b[i]=b[i-1] + a[i], c[i]=c[i-1];
//transformam vectorul a[i]=a[1]+...+a[i]
for(i=2;i<=n;i++)
a[i]+=a[i-1];
}
void solve()
{
int i;
for(i=k;i<=n;i++)
if(b[i-k+1] + a[i]-a[i-k+1] > smax)
smax=b[i-k+1] + a[i]-a[i-k+1],st=c[i-k+1],dr=i;
}
void write()
{
printf("%d %d %d\n",st,dr,smax);
}
int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
read();
init();
solve();
write();
fclose(stdin);
fclose(stdout);
return 0;
}