Cod sursa(job #2026911)

Utilizator tanasaradutanasaradu tanasaradu Data 25 septembrie 2017 12:33:56
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
const int nmax=100001;
///Complexitate O(n^2)
///dp[i]-sirul crescator maximal obtinut din subsecventa [1..i]
///mai exact care se termina pe pozitia i.
int a[nmax],dp[nmax],n,sol[nmax],k;
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>a[i];
    for(int i=1;i<=n;i++)
    {
        int mx=0;
        for(int j=i-1;j>=1;j--)
            if(a[i]>a[j] && mx<dp[j])
                mx=dp[j];
        dp[i]=1+mx;
    }
    int mx=-1,aux;
    for(int i=1;i<=n;i++)
        mx=max(mx,dp[i]);
    fout<<mx<<"\n";
    ///reconstruiesc solutia
    aux=LONG_MAX;
    int poz=n,t;
    while(mx)
    {
        bool ok=false;
        for(int i=poz;i>=1 && !ok;i--)
            if(dp[i]==mx && aux>a[i])
        {
            ok=true;
            ++k;
            sol[k]=a[i];
            aux=a[i];
            t=(i-1);
        }
        poz=t;
        mx--;
    }
    for(int i=k;i>=1;i--)
        fout<<sol[i]<<" ";
    fout<<"\n";
    fin.close();
    fout.close();
    return 0;
}