Pagini recente » Cod sursa (job #578159) | Cod sursa (job #1168209) | Cod sursa (job #2653958) | Cod sursa (job #3121113) | Cod sursa (job #3259208)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int n,mx,mn[5005],a[5005],k,l[5005];
void drum(int k){
for (int j=k;j>=1 && mx>0;j--){
if (l[j]==mx && a[j]<=a[k])
{
mx--;
drum(k);
fout<<j<<' ';
}
}
}
int main()
{
fin>>n;
mx=0;
mn[0]=-1000005;
for (int i=1;i<=n;i++){
fin>>a[i];
if (a[i]>=mn[mx]) mn[++mx]=a[i],k=i,l[i]=mx;
else {
int st=1,dr=mx,sol=0;
while (st<=dr){
int mij=(st+dr)/2;
if (mn[mij]>=a[i]) sol=mij,dr=mij-1;
else st=mij+1;
}
l[i]=sol-1;
mn[sol-1]=max(mn[sol-1],a[i]);
}
}
fout<<mx<<'\n';
drum(k);
return 0;
}