Cod sursa(job #2148417)

Utilizator VladimirPopa123Vladimir Popa VladimirPopa123 Data 1 martie 2018 18:31:37
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int a[100001],lung[100001],s[100001];

int main()
{
    int n,ns,pmax = 1;
    fin>>n;
    for(int i=1; i<=n; i++) fin>>a[i];
    for(int i=1; i<=n; i++)
    {
        lung[i] = 0;
        for(int j=1; j<=i-1; j++)
        {
            if(a[j] < a[i])
                if (lung[j] > lung[i]) lung[i] = lung[j];
        }
        lung[i]++;
        if (lung[i] > lung[pmax])
        {
            pmax = i;
        }
        //fout << lung[i] << " ";
    }
    //fout << "\n";
    ns=0;
    s[++ns]=pmax;
    int k=pmax-1;
    while(k)
    {
        if(a[k]<a[s[ns]]&&lung[k]==lung[s[ns]]-1) s[++ns]=k;
        k--;
    }
    fout<<lung[pmax]<<'\n';
    for(int i=lung[pmax]; i>=1; i--)
        fout<<a[s[i]]<<' ';
    return 0;
}
///3
///12 15 19