Cod sursa(job #1403981)
Utilizator | Zaharia Stefan Tudor stefzah | Data | 27 martie 2015 18:05:33 |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 70 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.57 kb |
#include <fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n,a[100001],t[100001],mx[100001],M,rez[100001],i,j,q,x;
int main()
{fin>>n;
M=1;
for(i=1;i<=n;i++)
fin>>a[i];
for(i=1;i<=n;i++)
{mx[i]=1;
for(j=1;j<=i-1;j++)
if((mx[j]+1>mx[i])&&(a[i]>a[j])){mx[i]=mx[j]+1;t[i]=j;
if(M<mx[i]){M=mx[i];q=i;}
}
}
fout<<M<<"\n";
i=q;
x=0;
while(i!=0)
{x++;
rez[x]=a[i];
i=t[i];
}
for(i=x;i>=1;i--)
fout<<rez[i]<<" ";
}