Cod sursa(job #1246848)

Utilizator stiharus96Dovan Andrei Dorinel stiharus96 Data 21 octombrie 2014 18:59:21
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
using namespace std;
ifstream f("date.in");
ofstream g("date.out");
int n,s[300],l[300],k,v[300],x,maxi,r,vect[300];
int cautbin(int a,int b,int x)
{
   int m=(a+b)/2;
    if(a==b)
        return a;
    if(x<s[m])
        cautbin(a,m,x);
   else if(x>s[m])
        cautbin(m+1,b,x);

}

int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
        f>>v[i];
    s[1]=v[1];
    l[1]=++k;
    for(int i=2;i<=n;i++)
    {
        if(v[i]>s[k])
        {
            l[i]=++k;
            s[k]=v[i];
        }
        else
        {
            x=cautbin(1,k,v[i]);
            s[x]=v[i];
            l[i]=x;
        }
    }
    for(int i=1;i<=k;i++)
        if(maxi<l[i])
            maxi=l[i];
    for(int i=n;i>=1;i--)
    {
        if(l[i]==maxi)
            maxi--;
            vect[++r]=v[i];
        if(maxi==0)
            break;
    }
    g<<r<<'\n';
    for(int i=r;i>=1;i--)
        g<<vect[i]<<" ";
    return 0;
}