Cod sursa(job #462381)
Utilizator | mihai995 mihai995 | Data | 10 iunie 2010 17:22:25 |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 70 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.51 kb |
#include <fstream>
using namespace std;
int v[1<<17],a[1<<17],p[1<<17];
ifstream in("scmax.in");
ofstream out("scmax.out");
void rec(int x)
{
if (!x)
return;
rec(p[x]);
out<<a[x]<<" ";
}
int main()
{
int i,j,n;
in>>n;
for (i=1;i<=n;i++)
in>>a[i];
v[1]=1;
for (i=2;i<=n;i++)
{
for (j=1;j<i;j++)
if (v[i]<v[j] && a[i]>a[j])
{
v[i]=v[j];
p[i]=j;
}
v[i]++;
}
for (i=j=1;i<=n;i++)
if (v[j]<v[i])
j=i;
out<<v[j]<<"\n";
rec(j);
return 0;
}