Cod sursa(job #1734133)

Utilizator UrsuDanUrsu Dan UrsuDan Data 26 iulie 2016 16:16:13
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <fstream>

using namespace std;

int l[100010];
int v[100010];

int main()
{
    int n,maxi,maxi2=0,ind,i,j;
    ifstream in ("scmax.in");
    ofstream out ("scmax.out");
    in>>n;
    for(i=1;i<=n;i++)
        in>>v[i];
    l[n]=1;
    for(i=n-1;i>=1;i--)
    {
        maxi=0;
        for(j=i+1;j<=n;j++)
            if(maxi<l[j] && v[i]<v[j])
                maxi=l[j];
        l[i]=maxi+1;
        if(maxi2<l[i])
        {
            maxi2=l[i];
            ind=i;
        }
    }
    out<<maxi2<<endl<<v[ind]<<" ";
    maxi2--;
    for(i=ind+1;i<=n;i++)
    {
        if(maxi2==l[i] && v[ind]<v[i])
        {
            maxi2--;
            ind=i;
            out<<v[i]<<" ";
        }
    }
    return 0;
}