Cod sursa(job #1807251)

Utilizator AlexVulpoiuAlexandru Vulpoiu AlexVulpoiu Data 16 noiembrie 2016 11:33:57
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstdio>
using namespace std;
int n,i,j,p,a[100001],b[100001];
int main()
{
    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;
    b[0]=1;
    p=n;
    for(i=n-1;i>=1;i--)
    {
        b[i]=0;
        for(j=i+1;j<=n;j++)
            if(a[i]<a[j] && b[j]>b[i])
                b[i]=b[j];
        b[i]++;
        if(b[i]>b[0])
        {
            b[0]=b[i];
            p=i;
        }
    }
    //for(i=1;i<=n;i++)
        //printf("%d ",b[i]);
    //printf("\n");
    printf("%d\n",b[0]);
    while(b[0])
    {
        printf("%d ",a[p]);
        for(j=p+1;j<=n;j++)
            if(b[j]==b[0]-1)
            {
                p=j;
                break;
            }
        b[0]--;
    }
    printf("\n");
    return 0;
}