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