Cod sursa(job #2438157)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 11 iulie 2019 14:50:28
Problema Subsir crescator maximal Scor 65
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>
using namespace std;

#define MAXN int(1e5)
typedef unsigned int uInt;

uInt a[MAXN], dp[MAXN], pre[MAXN], sol[MAXN];

int main()
{
    ifstream fin{"scmax.in"};
    ofstream fout{"scmax.out"};

    uInt N;

    fin>>N;

    for(uInt i=0; i<N; i++ )
        fin>>a[i], dp[i]=1;

    uInt max_poz{0}, max_len{0};

    for(uInt i=1; i<N; i++){
        for(uInt j=0; j<i; j++){
            if(a[i]>a[j] && dp[i]<dp[j]+1){
                dp[i] = dp[j] + 1;
                pre[i] = j;

                if(dp[i]>max_len){
                    max_poz = i;
                    max_len = dp[i];
                }
            }
        }
    }

    fout<<max_len<<endl;

    int k{-1};

    do{
        sol[++k] = a[max_poz];
        max_poz = pre[max_poz];

    } while(max_poz != 0);

    for(; k>=0; k--) fout<<sol[k]<<" ";
}