Cod sursa(job #2163374)

Utilizator PaduraruCristianPaduraru Cristian Daniel PaduraruCristian Data 12 martie 2018 17:59:33
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int v[100000],best[100000],poz[100000],n,M,p;


void citire()
{
    f>>n;
    for(int i=0;i<n;i++)
        f>>v[i];
    f.close();
}
void dinamic()
{
    best[n-1]=1;
    poz[n-1]=-1;
    int i,j;
    M=1;p=n-1;
    for(i=n-2;i>=0;i--)
    {
        best[i]=1;
        poz[i]=-1;
        for(j=i+1;j<n;j++)
        {
            if(v[i]<v[j]&&best[i]<=best[j])
            {
                best[i]=best[j]+1;
                poz[i]=j;
            }
        }
        if(best[i]>M)
            {M = best[i];p=i;}
    }
}
void afisare()
{

    int k=p;
    g<<M<<"\n";
    while(k!=-1)
    {
        g<<v[k]<<" ";
        k=poz[k];
    }
    g.close();
}

int main()
{
    int n;
    citire();
    dinamic();
    afisare();
    return 0;
}