Pagini recente » Cod sursa (job #1973651) | Cod sursa (job #1417946) | Cod sursa (job #1814168) | Cod sursa (job #2803019) | Cod sursa (job #1235376)
#include <iostream>
#include <fstream>
using namespace std;
int n,a[5001], best[5001], maxLength, sol[5001];
ifstream f("subsir2.in");
ofstream g("subsir2.out");
void readData()
{
f >> n;
for (int i = 1; i <= n; ++i) f >> a[i];
f.close();
}
void compute()
{
int max = 0, pos = 1, ok = 1;
best[1] = 1;
for (int i = 2; i <= n; ++i)
{
max = 0;
for (int j = 1; j < i; ++j)
{
if (a[j] <= a[i] && best[j]>max) max = best[j];
}
best[i] = max + 1;
}
for (int i = 2; i <= n; ++i) if (best[i] == 1) pos = i;
maxLength = 1;
sol[maxLength] = pos;
for (int i = pos; i <= n;)
{
max = 1000001;
ok = 0;
for (int j = i + 1; j <= n; ++j)
{
if (a[j] < max && best[j] == maxLength+1)
{
max = a[j];
pos = j;
ok = 1;
}
}
if (ok)
{
sol[++maxLength] = pos;
i = pos;
}
else break;
}
g << maxLength << "\n";
for (int i = 1; i <= maxLength; ++i) g << sol[i] << " ";
g.close();
}
int main()
{
readData();
compute();
return 0;
}