Pagini recente » Cod sursa (job #843150) | Cod sursa (job #498927) | Cod sursa (job #751589) | Cod sursa (job #1839077) | Cod sursa (job #283948)
Cod sursa(job #283948)
#include<stdio.h>
using namespace std ;
int a[5001], sis[5001], next[5001], n, valmin ;
int main()
{
int i, j, min, max, poz, val, t, pmax ;
freopen("subsir2.in","r",stdin) ;
freopen("subsir2.out","w",stdout) ;
scanf("%d", &n) ;
for (i=1 ; i<=n ; i++)
scanf("%d",&a[i]) ;
max = 1 ; pmax = n ; valmin = a[n] ;
sis[n] = 1 ;
next[n] = 0 ;
for (i=n-1 ; i>=1 ; i--)
{
min = 0 ;
val = 5000001 ;
poz = n+1 ;
t = a[i] ;
for (j=i+1 ; j<=n ; j++)
if ((min<=sis[j])&&(t<=a[j])&&(a[j]<val))
{
min = sis[j] ;
poz = j ;
val = a[j] ;
}
if (poz <= n)
{
min++ ;
sis[i] = min ;
next[i] = poz ;
if (max < min) { max = min ; pmax = i ; valmin = a[pmax] ;}
else if ((max == min)&&(a[i]<valmin))
valmin = a[i] ;
}
else
{
sis[i] = 1 ;
next[i] = 0 ;
}
}
//for (i=1 ; i<=n ; i++)
// printf("%d ",next[i]) ;
printf("%d\n",max) ;
while (max >= 1)
{
printf("%d ", pmax) ;
max-- ;
min = 5000001 ;
for (i=pmax ; i<=n ; i++)
if ((sis[i] == max)&&(min>a[i])&&(a[i]>=valmin))
{
min = a[i] ;
pmax = i ;
}
valmin = min ;
}
printf("\n") ;
return 0 ;
}