Cod sursa(job #1811037)

Utilizator al_k_ponyClaudiu Babin al_k_pony Data 20 noiembrie 2016 19:46:53
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 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];
vector<int> dp[100005];
pair <int,int> mx;

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].push_back(a[i]);
        for(int j = i;j>=1;j--)
        {
            if(a[j] < a[i] && dp[j].size() + 1 > dp[i].size())
                {dp[i]=dp[j];dp[i].push_back(a[i]);}
        }
        if(dp[i].size()>mx.second) mx = {i,dp[i].size()};
    }
    cout << mx.second << '\n';
    for(int i = 0;i<mx.second;i++)
        cout << dp[mx.first][i] << ' ';
}