Pagini recente » Cod sursa (job #2954293) | Cod sursa (job #1107332) | Cod sursa (job #1429678) | Cod sursa (job #1580877) | Cod sursa (job #2156632)
#include <fstream>
#include <iostream>
#include <stack>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int a[100002];
int best[100002];
int prev[100002];
int n;
int maxi=-1;
int imax=-1;
int max_best(int val, int pos)
{
int fmaxi=-1;
int fimax=-1;
for(int i=1; i<=pos; i++)
if(a[i]<val)
if(fmaxi<best[i])
{
fmaxi=best[i];
fimax=i;
}
return fimax;
}
int main()
{
fin >> n;
for(int i=1; i<=n; i++)
{
fin >> a[i];
int posmax=max_best(a[i], i);
if(posmax!=-1)
{
best[i]=best[posmax]+1;
prev[i]=posmax;
if(maxi<best[i])
{
maxi=best[i];
imax=i;
}
}
else
{
best[i]=1;
prev[i]=-1;
if(maxi<best[posmax])
{
maxi=best[i];
imax=i;
}
}
}
fout << maxi << '\n';
stack <int> s;
for(int i=imax; i>0; )
{
s.push(a[i]);
i=prev[i];
}
while(!s.empty())
{
fout << s.top() << " ";
s.pop();
}
return 0;
}