Cod sursa(job #3252203)

Utilizator Alexbora13Bora Ioan Alexandru Alexbora13 Data 28 octombrie 2024 20:02:08
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

const int NMAX = 100000;

int n, maxi = 0;
int v[NMAX + 1];
int dp[NMAX + 1], pos[NMAX + 1], p = 0;

int main() 
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> v[i];

    for (int i = 1; i <= n; i++) 
    {
        dp[i] = 1;
        pos[i] = 0;
    }

    for (int i = 2; i <= n; i++) 
    {
        for (int j = 1; j < i; j++) 
        {
            if (v[i] > v[j]) 
            {
                if (dp[j] + 1 > dp[i]) 
                {
                    dp[i] = dp[j] + 1;
                    pos[i] = j;
                }
            }
        }
        if (dp[i] > maxi) 
        {
            maxi = dp[i];
            p = i;
        }
    }

    vector<int> ans;
    while (p) 
    {
        ans.push_back(v[p]);
        p = pos[p];
    }

    fout << ans.size() << '\n';
    reverse(ans.begin(), ans.end());
    for (int x : ans)
        fout << x << ' ';

    return 0;
}