Mai intai trebuie sa te autentifici.
Cod sursa(job #698850)
Utilizator | Data | 29 februarie 2012 16:26:05 | |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 40 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.08 kb |
#include <fstream>
using namespace std;
int bst[100069],smax[100069];
int main()
{
int i,j,n,max,sir[100069],inmax;
ifstream in ("scmax.in");
ofstream out ("scmax.out");
in>>n;
for (i=1;i<=n;i++)
in>>sir[i];
bst[1]=1;
for (i=2;i<=n;i++)
{
max=0;
for (j=i-1;j>=1;j--)
{
if (max<=bst[j])
{
if (sir[i]>sir[j])
{
bst[i]=bst[j]+1;
max=bst[j];
}
}
}
if (bst[i]==0)
bst[i]=1;
}
max=1;
for (i=1;i<=n;i++)
{
if (bst[i]>max)
max=bst[i];
}
out<<max<<"\n";
inmax=1;
for (i=1;i<=n;i++)
{ if (bst[i]>=inmax)
{
smax[bst[i]]=sir[i];
inmax=bst[i];
}
}
for (i=1;i<=max;i++)
out<<smax[i]<<" ";
out<<"\n";
/*for (i=1;i<=n;i++)
out<<sir[i]<<" ";
out<<"\n";
for (i=1;i<=n;i++)
out<<bst[i]<<" ";*/
return 0;
}