Cod sursa(job #3286815)

Utilizator Andrei24543Andrei Hulubei Andrei24543 Data 14 martie 2025 18:17:53
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>
using namespace std;

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

int n , a[100005] , dp[100005] , urm[100005];

int main()
{
    int i , j , mx , p;
    fin >> n;
    for(i = 1;i <= n;i++)
        fin >> a[i];
    dp[n] = 1;
    urm[n] = n + 1;
    for(i = n - 1;i >= 1;i--)
    {
        mx = 0; p = n + 1;
        for(j = i + 1;j <= n;j++)
            if(a[i] < a[j] and dp[j] > mx)
            {
                mx = dp[j];
                p = j;
            }
        dp[i] = mx + 1;
        urm[i] = p;
    }

    mx = 0;
    for(i = 1;i <= n;i++)
        if(dp[i] > mx)
        {
            mx = dp[i];
            p = i;
        }

    fout << mx << "\n";
    while(p != n + 1)
    {
        fout << a[p] << " ";
        p = urm[p];
    }
    return 0;
}
/***/