Pagini recente » Cod sursa (job #84511) | Cod sursa (job #1432661) | Cod sursa (job #2716009) | Cod sursa (job #619293) | Cod sursa (job #2385376)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("subsir2.in");
ofstream fout ("subsir2.out");
int n, a[5005], dp[5005], lg, last = INT_MIN;
void Solve(int dim, int pos)
{
int cand_pos, cand_nr = INT_MAX;
for (int i = pos + 1; i <= n; i++)
{
if (dp[i] == dim && a[i] >= last)
{
if (a[i] < cand_nr)
{
cand_nr = a[i];
cand_pos = i;
}
}
}
fout << cand_pos << " ";
last = cand_nr;
if (dim >= 2)
Solve(dim - 1, cand_pos);
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
fin >> a[i];
for (int i = n; i >= 1; i--)
{
dp[i] = 1;
for (int j = i + 1; j <= n; j++)
{
if (a[i] <= a[j] && dp[i] < dp[j] + 1)
dp[i] = dp[j] + 1;
}
}
for (int i = 1; i <= n; i++)
lg = max(lg, dp[i]);
fout << lg << "\n";
Solve(lg, 0);
return 0;
}