Pagini recente » Cod sursa (job #2889202) | Cod sursa (job #1222573) | Atasamentele paginii Clasament 1770673153154766 | Istoria paginii runda/arhiva-vianu | Cod sursa (job #342491)
Cod sursa(job #342491)
#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=V[i];
for (j=i+1;j<=N;++j)
{
if (V[i]<V[j] && best[i]<best[j]+1 && V[j]<min)
{
best[i]=best[j]+1;
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;
}