Pagini recente » Cod sursa (job #950835) | Cod sursa (job #2269933) | Cod sursa (job #1998077) | Cod sursa (job #528515) | Cod sursa (job #1533944)
#include <fstream>
#define INF (1 << 30)
using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int n, a[5001], b[5001], min1[5001], p1[5001];
int i, j, max1;
int main()
{
f >> n;
for (i = 1; i <= n; i++)
f >> a[i];
for (i = n; i >= 1; i--)
{
max1 = 0;
for (j = i+1; j <= n; j++)
if (a[j] > a[i] && max1 < b[j])
max1 = b[j];
b[i] = max1+1;
if (b[i] > max1)
max1 = b[i];
}
for (i = 1; i <= max1; i++)
min1[i] = INF;
min1[max1+1] = -INF, p1[max1+1] = -1;
for (i = 1; i <= n; i++)
{
//g << b[i] << " ";
if (min1[b[i]] > a[i] && a[i] > min1[b[i]+1] && p1[b[i]+1] < i)
min1[b[i]] = a[i], p1[b[i]] = i;
}
g << max1 << "\n";
for (i = max1; i >= 1; i--)
g << p1[i] << " ";
return 0;
}