Cod sursa(job #2042614)

Utilizator DdariusDarius Ddarius Data 18 octombrie 2017 20:53:27
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#include<stack>

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

int n, v[100005], dp[100005], mx=-1, i, j, a, p;
stack<int> s;

int main()
{
    f>>n;
    dp[1]=1;
    for(i=1; i<=n; i++)
    {
        f>>v[i];
    }
    for(i=2; i<=n; i++)
    {
        for(j=i-1; j>=1; j--)
        {
            if(v[i]>v[j]&&dp[j]>dp[i])
            {
                dp[i]=dp[j]+1;
            }
            if(dp[i]>mx)
            {
                mx=dp[i];
            }
        }
        if(dp[i]==0)
            dp[i]=1;
    }
    cout<<mx<<'\n';
    p=mx;
    while(n>0)
    {
        if(dp[n]==p)
        {
            s.push(v[n]);
            p--;
        }
        n--;
    }
    while(!s.empty())
    {
        cout<<s.top()<<' ';
        s.pop();
    }
    return 0;
}