Pagini recente » Cod sursa (job #1115456) | Cod sursa (job #305772) | Cod sursa (job #1019846) | Cod sursa (job #1825507) | Cod sursa (job #49778)
Cod sursa(job #49778)
#include <stdio.h>
int n, v[5001], a[5001], prev[5001];
void print(int pos);
int main()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
int i, min, mid, max, cnt, sol, j, m;
scanf("%d", &n);
for(i = 1; i <= n; ++i)
{
scanf("%d", &v[i]);
}
m = 1;
for(i = 2; i <= n; ++i)
{
if(v[i] < v[m])
m = i;
}
a[0] = 0;
v[0] = -1000001;
a[1] = m;
cnt = 1;
for(i = m + 1; i <= n; ++i)
{
min = 0;
max = cnt;
sol = cnt;
while(min <= max)
{
mid = (min + max) >> 1;
if(v[a[mid]] <= v[i])
{
min = mid + 1;
sol = mid;
}
else
{
max = mid - 1;
}
}
a[sol + 1] = i;
prev[i] = a[sol];
if(sol + 1 > cnt)
cnt = sol + 1;
/*
for(j = 1; j <= cnt; ++j)
{
printf("%d ", v[a[j]]);
}
printf("\n");
*/
}
printf("%d\n", cnt);
print(a[cnt]);
return 0;
}
void print(int pos)
{
if(pos)
{
print(prev[pos]);
printf("%d ", pos);
}
}