Pagini recente » Istoria paginii runda/dinamica_1 | Cod sursa (job #2216139) | Istoria paginii utilizator/milealoredana19 | lasm_28.11.2018 | Cod sursa (job #907320)
Cod sursa(job #907320)
#include<iostream>
#include<cstdio>
#include<climits>
#define maxn 100010
using namespace std;
int x[maxn],L[maxn],P[maxn],i,j,n,Max,Min,poz,p,k,val,start;
int main()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
scanf("%d", &n);
for(i=1; i<=n; ++i)
scanf("%d",&x[i]);
for(i=n; i>0; --i)
{
Min = INT_MAX; poz=n+1;
val = INT_MAX;
L[i] = 1; P[i] = -1;
for(j=i+1; j<=n; ++j)
if (x[i] <= x[j])
{
if(Min > L[j] && x[j] < val)
{
Min = L[j];
poz = j; P[i] = j;
val = x[j];
}
else if (Min==L[j] && x[j]==x[poz]) poz=j;
}
if (poz <= n) L[i]= 1 + Min, P[i]=poz;
if(L[i] >= Max) Max = L[i], start = i;
}
printf("%d\n",Max);
while(start!=-1)
cout<<start<<" ", start=P[start];
return 0;
}