Cod sursa(job #1810982)

Utilizator al_k_ponyClaudiu Babin al_k_pony Data 20 noiembrie 2016 18:56:49
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
# define maxn 100005
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define _ ios_base::sync_with_stdio(false);cin.tie(0);
# define pb push_back
# define mp make_pair
using namespace std;

vector<int>vec;
int n,a[100005],pre[100005];
pair <int,int> dp[100005];

void constr(int pos,int k)
{
    if(k > dp[n].first) return;
    vec.push_back(a[pos]);
    constr(dp[pos].second,k+1);
}

int main(){_
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    cin >> n;
    for(int i = 1;i<=n;i++)
        cin >> a[i];
    for(int i = 1;i<=n;i++)
    {
        dp[i]={1,i};
        for(int j = i;j>=1;j--)
        {
            if(a[j] < a[i] && dp[j].first + 1 > dp[i].first)
                dp[i] = {dp[j].first+1,j};
        }
    }
    cout << dp[n].first << '\n';
    constr(n,1);
    for(int i = vec.size()-1;i>=0;i--)
        cout << vec[i] << ' ';
}