Pagini recente » Cod sursa (job #1315748) | Cod sursa (job #1103399)
#include<fstream>
using namespace std;
const int MAXN=100005;
int n,SOL_MAX,POZ_MAX;
int a[MAXN],next_cell[MAXN],lis[MAXN];
void read()
{
ifstream fin("scmax.in");
fin>>n;
for (int i=1; i<=n; lis[i]=1, ++i)
fin>>a[i];
fin.close();
}
void write()
{
ofstream fout("scmax.out");
fout<<lis[POZ_MAX]<<'\n';
for (int i=POZ_MAX; i!=0; i=next_cell[i])
fout<<a[i]<<' ';
fout.close();
}
void solve()
{
int i,j;
for (i=n-1; i>=1; --i)
{
for (j=i+1; j<=n; ++j)
{
if (1+lis[j]>lis[i] && a[j]>a[i])
{
lis[i]=1+lis[j];
next_cell[i]=j;
}
}
if (lis[i]>lis[POZ_MAX])
POZ_MAX=i;
}
}
int main()
{
read();
solve();
write();
return 0;
}