Cod sursa(job #2830397)

Utilizator Mihai_EduardMihai Eduard Mihai_Eduard Data 9 ianuarie 2022 20:59:53
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");
const int NMAX=100005;

/// dp[i]=lungimea a a subsirului crescator de incepe din i
int N, v[NMAX], dp[NMAX], T[NMAX], sol, st;

int main()
{
    fin>>N;
    for(int i=1;i<=N;i++)
        fin>>v[i];

    int maxim=0;
    dp[N]=1;
    sol=1;
    st=N;
    for(int i=N-1;i>=1;i--){
        maxim=0;
        for(int j=i+1;j<=N;j++){
            if(v[j]>v[i]){
                if(dp[j]>maxim){
                    maxim=dp[j];
                    T[i]=j;
                }
            }
        }
        dp[i]=maxim+1;
        if(dp[i]>sol){
            sol=dp[i];
            st=i;
        }
    }

    fout<<sol<<'\n';
    fout<<v[st]<<' ';
    while(T[st]!=0){
        st=T[st];
        fout<<v[st]<<' ';
    }

    fin.close();
    fout.close();
}