Pagini recente » Cod sursa (job #1598281) | Monitorul de evaluare | Cod sursa (job #1124091) | Cod sursa (job #2030502) | Cod sursa (job #2029200)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int n, i, j, nr, v[5011], mx, rez[5010];
int best[5010], pre[5010], in;
int main()
{
fin >> n;
for (i = 1; i <= n; i++)
fin >> v[i];
best[1] = 1;
for (i = 2; i <= n; i++)
{
mx = 0;
for (j = 1; j < i; j++)
{
if (v[j] < v[i] && best[j] > mx)
{
mx = best[j];
pre[i] = j;
}
if (v[j] < v[i] && best[j] == mx && v[j] <= v[pre[i]])
pre[i] = j;
}
best[i] = mx + 1;
}
mx = 0;
for (i = 1; i <= n; i++)
{
if (best[i] > mx)
{
mx = best[i];
in = i;
}
if (best[i] == mx && v[i] < v[in])
in = i;
}
i = in;
while (i != 0)
{
nr++; rez[nr] = i;
i = pre[i];
}
fout << nr << "\n";
for (i = nr; i >= 1; i--) fout << rez[i] << " ";
return 0;
}