Cod sursa(job #2358290)

Utilizator Ciprian_PizzaVasile Capota Ciprian_Pizza Data 27 februarie 2019 23:11:27
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>
#define nmax 100005

using namespace std;

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

int n,a[nmax],dp[nmax],len,poz,pre[nmax];

int main()
{
    int i,j;
    fin >> n;
    for(i = 1; i <= n; i++)
        fin >> a[i];
    dp[n] = 1;
    pre[n] = -1;
    poz = n;
    len = 1;
    for(i = n-1; i >= 1; i--)
    {
        for(j = i+1; j <= n; j++)
            if(dp[j] > dp[i] && a[i] < a[j])
            {
                dp[i] = dp[j] + 1;
                pre[i] = j;
                if(dp[i] > len)
                {
                    len = dp[i];
                    poz = i;
                }
            }
        if(dp[i] == 0) dp[i] = 1;
    }
    fout << len << "\n";
    while(poz!=-1)
    {
        fout << a[poz] << " ";
        poz = pre[poz];
    }

    fin.close();
    fout.close();
    return 0;
}