Cod sursa(job #2083880)

Utilizator CezShreddRBretan Cezar CezShreddR Data 8 decembrie 2017 11:42:32
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("data.in");
ofstream g ("data.out");
long long a[100001];
int dp[100001],ind[100001];
int main()
{
    int n,i,j,macs,lmax=0,poz=0;
    f>>n;
    for(i=1;i<=n;i++)
        f>>a[i];
    dp[n]=1;
    ind[n]=0;
     for(i=n-1;i>=1;i--)
    {
        macs=0;
        for(j=i+1;j<=n;j++)
            if(a[i]<a[j] && dp[j]>macs) {macs=dp[j];ind[i]=j;}
        if(!macs) ind[i]=0;
        dp[i]=1+macs;
        if(dp[i]>lmax) {lmax=dp[i];poz=i;}
    }
    g<<lmax<<'\n';
    while(poz) {g<<a[poz]<<' ';poz=ind[poz];}

    return 0;
}