Cod sursa(job #3167046)

Utilizator Dia3141Costea Diana Stefania Dia3141 Data 9 noiembrie 2023 22:06:21
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
using namespace std;
ifstream cin("scmax.in");
ofstream cout("scmax.out");
int n,i,j,Max,p,u,sol,v[100001],d[100001],poz[100001];
void drum(int u){  ///determin elementele din sirul crescator
    if(u!=0){
        drum(poz[u]);
        cout<<v[u]<<" ";
    }
}
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i];
    d[1]=1;
    for(i=2;i<=n;i++){
        Max=0;
        for(j=1;j<i;j++){///ma folosesc de sirurile maxime determinate anterior si verific daca pot adauga la final pe v[i]
            if(v[i]>v[j]&&d[j]>Max){
                Max=d[j];
                p=j;
            }
        }
        d[i]=Max+1;
        if(d[i]!=1)  ///adaug pozitia in cazul in care lungimea sirului crescator terminat in i, care contine pe v[i], care are mai mult de un element
            poz[i]=p;
        if(d[i]>sol){ ///determin lungimea maxima
            sol=d[i];
            u=i;
        }
    }
    cout<<sol<<'\n';
    drum(u);
    return 0;
}