Cod sursa(job #1726639)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 8 iulie 2016 16:06:10
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#define NMAX 100005
#define ll long long
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");

int dp[NMAX];
int n;
int a[NMAX];
int scl=0;

void cit()
{
    f>>n;
    for(int i=0; i<n; i++)
        f>>a[i];
}

void print(int poz)
{
    g<<scl<<"\n";
    g<<a[poz]<<" ";
    int k=dp[poz]-1;
    int o=poz;
    for(int i=poz+1;i<n;i++)
        if(dp[i]==k&& a[i]>a[o])
        {
            k--;
            o=i;
            g<<a[i]<<" ";
        }
}

int maxi(int i)
{
    int maxi=0;
    for(int ii=i+1; ii<n; ii++)
        if(dp[ii]>dp[maxi]&&a[ii]>a[i])
            maxi=ii;
    return maxi;
}


int main()
{

    int pozu;
    cit();
    dp[n-1]=1;
    for(int i=n-2; i>=0; i--)
    {
        dp[i]=1+dp[maxi(i)];
        if(dp[i]>scl)
            {
                scl=dp[i];pozu=i;
            }
    }
    print(pozu);


    return 0;
}