Cod sursa(job #1993572)

Utilizator victoreVictor Popa victore Data 23 iunie 2017 12:00:35
Problema Secventa 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<cstdio>

const int nmax=50005;

int v[nmax];
int l=1,r=1,sumusmaximus;

inline void find_max(int start,int finish)
{
    int besti=start,bestj=start,st,dr,sum=0,summax=v[start];
    for(st=dr=1;dr<=finish;++dr)
    {
        if(sum<0)
            sum=v[dr],st=dr;
        else
            sum+=v[dr];
        if(sum>summax)
        {
            besti=st;
            bestj=dr;
            summax=sum;
        }
    }
    if(summax>sumusmaximus)
    {
        sumusmaximus=summax;
        l=besti;
        r=bestj;
    }
}

int main()
{
    freopen("secv2.in","r",stdin);
    freopen("secv2.out","w",stdout);
    int n,i,j,k;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n&&scanf("%d",&v[i]);++i);
    sumusmaximus=v[1];
    for(i=0;i+k<=n;++i)
        find_max(1+i,k+i);
    printf("%d %d %d",l,r,sumusmaximus);
}