Cod sursa(job #2680430)

Utilizator Xutzu358Ignat Alex Xutzu358 Data 3 decembrie 2020 15:29:00
Problema Subsir crescator maximal Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

int dp[100005];
int pre[100005];
int v[100005];
int n;
int sirmax;
int pozmax;
stack < int > st;
int ctr;

int main()
{
    f >> n;
    for (int i=1;i<=n;i++) {
        f >> v[i];
    }
    dp[1]=1;
    for (int i=2;i<=n;i++) {
        for (int j=1;j<i;j++) {
            if (v[i]>v[j] && dp[j]+1>dp[i]) {
                    dp[i]=dp[j]+1;
                    pre[i]=j;
                    if (dp[i]>sirmax) {
                        sirmax = dp[i];
                        pozmax = i;
                    }
            }
        }
    }
    while (pozmax!=0) {
        st.push(v[pozmax]);
        ctr++;
        pozmax = pre[pozmax];
    }
    g << ctr << '\n';
    while (st.empty()==0) {
        g << st.top()<<" ";
        st.pop();
    }
    return 0;
}