Pagini recente » Echipa infoarena | Monitorul de evaluare | Rating Gasca Giorgiana (Giorgi) | Rating Matei Balaur12 (matei.balaur2009) | Cod sursa (job #2062764)
//http://www.infoarena.ro/problema/scmax Subsir crescator maximal
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
int n, v[100005],mx,b[100005],sol[100005], l,rez;
void best(int arr[]);
void construire();
int main()
{
fin >> n;
for(int i=1; i<=n; i++)
fin >> v[i];
best(v);
construire();
fout << rez <<"\n";
for(int i=1; i<=rez; i++)
fout << sol[i] << " ";
}
void best(int arr[])
{
b[1]=1;
for(int i=2; i<=n; i++)
{
mx=0;
for(int j=1; j<=i-1; j++)
{
if(arr[j]<arr[i] && mx<b[j])
mx=b[j];
}
b[i]=mx+1;
}
}
void construire()
{
int m=1;
for(int i=2; i<=n; i++)
if(b[i]>b[m])
m=i;
l=b[m];
rez=l;
sol[l]=v[m];
int i;
while(b[m]>1)
{
i=m-1;
while(v[i]>=v[m] || b[i]!=b[m]-1)
i--;
m=i;
l--;
sol[l]=v[m];
}
}