QBDIVSEQ - Chia dãy

Tác giả: hieult

Ngôn ngữ: C++

#include <stdio.h>
//#include <conio.h>

int main()
{
    int n,f[100001],a[100001],t;
    scanf("%d",&n);
    for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
    t = 1;
    f[1] = a[1];
    for(int i = 2;i<=n;i++)
    {
        if(a[i]<f[t])
        {
            t++;
            f[t] = a[i];
        }
        else if(a[i]>=f[1]) f[1] = a[i];
        else
        {
            int u = 1,v = t,r;
            while(v-u>1)
            {
                r = (u+v)/2;
                if(a[i]<f[r])
                    u = r;
                else v = r;
            }
        
        f[v] = a[i];
        }
    }
    printf("%d",t);
    //getch();
}
    

Download