Pagini recente » Istoria paginii runda/9-10_cecererece | Cod sursa (job #2942177) | Cod sursa (job #2142288) | Cod sursa (job #167734) | Cod sursa (job #342682)
Cod sursa(job #342682)
#include <cstdio>
#define Nmax 5100
#define Inf 0x3f3f3f3f
int V[Nmax],N,max,p,poz[Nmax],best[Nmax],i,j,min;
void read_data()
{
freopen("subsir2.in","r",stdin);
scanf("%d\n", &N);
for (i=1;i<=N;++i)
scanf("%d ", &V[i]);
}
void find_max()
{
best[N]=1;
poz[N]=-1;
max=0;
p=N;
//min=Inf;
for (i=N-1;i>=1;--i)
{
best[i]=1;
poz[i]=-1;
//if (V[i]<=min)
min=Inf;
for (j=i+1;j<=N;++j)
{
if (V[i]<V[j] && V[j]<min)
{
if (best[i]>best[j]+1)
{
best[i]=best[j]+1;
poz[i]=j;
}
else
if (best[j]+1==best[i])
if (V[j]<V[poz[i]])
poz[i]=j;
min=V[j];
if (best[i]>max)
{
max=best[i];
p=i;
}
}
}
}
}
void constr_sir()
{
int j,ok;
i=p;
while (i!=-1)
{
ok=1;
//printf("%d ", V[i]);
for (j=1;j<=N && ok;++j)
if (V[i]==V[j])
{
printf("%d ", j);
//break;
ok=0;
}
i=poz[i];
}
}
void write_data()
{
freopen("subsir2.out","w",stdout);
printf("%d\n", max);
}
int main()
{
read_data();
find_max();
write_data();
constr_sir();
return 0;
}