Cod sursa(job #2922216)

Utilizator Milka69Anastase Luca George Milka69 Data 6 septembrie 2022 12:02:45
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMAX = 100005;
int arr[NMAX], n, dp[NMAX];
vector<int>v;

inline void solve()
{
    int ans = 0, poz;
    for(int i=0;i<n;++i)
    {
        dp[i] = 1;
        for(int j=0;j<i;++j)
        {
            if(arr[i] > arr[j])
                dp[i] = max(dp[i],dp[j]+1);
        }
        if(ans < dp[i])
        {
            poz = i;
            ans = dp[i];
        }
    }
    g << ans << '\n';
    int cnt = ans-1;
    v.push_back(arr[poz]);
    for(int i=poz-1;i>=0;--i)
    {
        if(dp[i] == cnt && arr[i] < v[v.size()-1])
        {
            v.push_back(arr[i]);
            cnt--;
        }
    }
    for(int i=v.size()-1;i>=0;--i)
        g << v[i] << ' ';
}

int main()
{
    f >> n;
    for(int i=0;i<n;++i)
        f >> arr[i];
    solve();
}