NKMAXSEQ - Dãy con dài nhất

Tác giả: hieult

Ngôn ngữ: C++

#include <cstdio>
//#include <conio.h>
#include <algorithm>

int main()
{
   // freopen("NKMAXSEQ.in","r",stdin);
    int n,p,u[50001],Id[50001],x;
    scanf("%d %d",&n,&p);
    int min=0,imin=0;
    u[0]=0;
    for(int i = 1;i<=n;i++)
    {
        scanf("%d",&x);
        u[i] = u[i-1]+x;
        if(u[i]<min)
        {
            min = u[i];
            imin = i;
        }
        Id[i] = imin;
    }
    int i = Id[n],j=n,t=0;
    while(true)
    {
        while(i<j && j-i>t && u[j]-u[i]<p) j--;
        if(j-i>t)
            t = j-i;
        if(i==0) break;
        i = Id[i-1];
    }
    if(t==0)
       printf("-1");
    else printf("%d",t);
   // getch();
}

Download