Pagini recente » Cod sursa (job #2974714) | Cod sursa (job #368246) | Cod sursa (job #3230331) | Cod sursa (job #933148) | Cod sursa (job #2496843)
#include <fstream>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int a[5005], lis[5005], n;
int main()
{
fin >> n;
for(int i = 1; i <= n; i++)
fin >> a[i];
lis[n] = 1;
int M;
for(int i = n - 1; i > 0; i--)
{
M = 0;
for(int j = i + 1; j <= n; j++)
if(lis[j] > M && a[j] >= a[i])
M = lis[j];
lis[i] = 1 + M;
}
/**for(int i = n - 1; i > 0; i--)
{
Min1 = Min2 = 1e9;
for(int j = i + 1; j <= n; j++)
if(a[j] >= a[i] && a[j] < Min1)
{
if(lis[j] < Min2) Min2 = lis[j];
Min1 = a[j];
}
if(Min2 == 1e9) lis[i] = 1;
else lis[i] = 1 + Min2;
}
Min = ans = 1e9;
for(int i = 1; i <= n; i++)
if(a[i] < Min)
{
Min = a[i];
ans = min(ans, lis[i]);
}
*/
int p = 1;
for(int i = 2; i <= n; i++)
if(lis[i] > lis[p])
p = i;
fout << lis[p] <<"\n" << p << " ";
int poz, ult = p, L, Min;
for(L = lis[p] - 1; L > 0; L--)
{
Min = 1e9;
for(int i = p + 1; i <= n; i++)
if(a[i] >= a[ult] && a[i] < Min && lis[i] == L)
{
Min = a[i];
poz = i;
}
p = ult = poz;
fout << p << " ";
}
return 0;
}