Cod sursa(job #945017)

Utilizator vlady1997Vlad Bucur vlady1997 Data 30 aprilie 2013 11:06:17
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
        #include <cstdio>
        using namespace std;
        int a[100001], b[100001],mx;
        int main()
        {
            int n, m, i, j, max, u, p;
            freopen("scmax.in","r",stdin);
            freopen("scmax.out","w",stdout);
            scanf("%d",&n);
            for (i=1; i<=n; i++) scanf("%d",&a[i]);
            b[n]=1;mx=0;
            for (i=n-1; i>=1; i--)
            {
                max=0;
                for (j=i+1; j<=n; j++)
                {
                    if (a[i]<a[j] && max<b[j]) max=b[j];
                }
                b[i]=max+1;
                if (b[i]>mx)
                {
                    mx=b[i];
                    p=i;
                }
            }
            printf("%d\n%d ",mx,a[p]);
            mx--; u=a[p];
            for (i=p+1; i<=n; i++)
            {
                if (a[i]>u && mx==b[i])
                {
                    mx--;
                    printf("%d ",a[i]);
                    u=a[i];
                }
            }
            return 0;
        }