Cod sursa(job #1784695)
Utilizator | Andrei Nedelcu Darn | Data | 20 octombrie 2016 13:16:24 |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.62 kb |
#include <fstream>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int n,v[100001],best[100001],pr[100001],i,j,ma=0,mai;
void refacere(int k)
{
if(pr[k]!=-1)
refacere(pr[k]);
out<<v[k]<<" ";
}
int main()
{
in>>n;
for (i=1;i<=n;i++)
in>>v[i];
for (i=1;i<=n;i++)
{
best[i]=1;
pr[i]=-1;
for (j=1;j<i;j++)
{
if (v[j]<v[i]&&best[j]>=best[i])
{best[i]=1+best[j]; pr[i]=j;}
}
if (best[i]>ma) {ma=best[i]; mai=i;}
}
out<<ma;
refacere(mai);
return 0;
}