Pagini recente » Cod sursa (job #3037825) | Cod sursa (job #2719552) | Cod sursa (job #1284223) | Cod sursa (job #2024814) | Cod sursa (job #1112009)
//Subsir crescator maximal
#include<iostream>
#include<fstream>
using namespace std;
int main()
{
ifstream f("scmax.in");
ofstream g("scmax.out");
long n,i,j,maxlg,pozm,nr;
long long a[100001],pozd[100001],lg[100001];
f>>n;
for ( i=1; i<=n; i++)
f>>a[i];
lg[n]=1;
pozd[n]=0;
maxlg=0;
for ( i=n-1; i>=1; i--) {
for (j=i+1; j<=n; j++)
//caut maximul din lg[j]
if (lg[j]>maxlg)
if (a[j]>a[i]){
maxlg=lg[j];
pozm=j;
}
//pun valorile
lg[i]=maxlg+1;
pozd[i]=pozm;
}
//Aflu lungimea maxima
maxlg=0;
for (i=1; i<=n; i++)
if (maxlg<lg[i]){
maxlg=lg[i];
pozm=i;
}
g<<pozm<<'\n';
nr=0;
i=pozm;
while (nr<maxlg)
{
g<<a[i]<<" ";
i=pozd[i];
nr++;
}
f.close();
g.close();
return 0;
}