Cod sursa(job #2669945)

Utilizator stephenieCosmina Stefania stephenie Data 8 noiembrie 2020 15:09:04
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int v[100002],dp[100002],t[100002];
int n,i,j,maxx,poz;
void rec(int poz)
{
    if(poz>0)
        {
        rec(t[poz]);
        fout<<v[poz]<<" ";
        }
}
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];

    for(i=1;i<=n;i++)
    {
        dp[i]=1;

        for(j=i-1;j>=1;j--)
            if(v[i]>v[j]&&dp[i]<dp[j]+1)
        {
            dp[i]=dp[j]+1;
            t[i]=j;

            if(maxx<dp[i])
            {
                maxx=dp[i];
                poz=i;
            }
        }
    }

 fout<<maxx<<'\n';
 rec(poz);

    return 0;
}