Pagini recente » Cod sursa (job #1993816) | Cod sursa (job #973967) | Cod sursa (job #1217668) | Cod sursa (job #2204640) | Cod sursa (job #1761368)
#include <fstream>
#include <iostream>
#define INF 1000010
using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int n, v[5005], best[5005], poz[5005], p, sol, minn[5005];
void Solve()
{
// I < J MEREU
best[n] = 1;
poz[n] = -1;
for(int i = n - 1; i >= 1; --i)
{
best[i] = 1;
poz[i] = -1;
for(int j = i + 1; j <= n; ++j)
{
if(v[i] <= v[j] && best[i] < best[j] + 1)
{
best[i] = best[j] + 1;
poz[i] = j;
if(best[i] > sol)
{
sol = best[i];
p = i;
}
minn[i] = v[j];
}
else if(v[i] <= v[j] && best[i] == best[j] + 1)
{
if( v[j] < minn[i])
{
minn[i] = v[j];
poz[i] = j;
}
}
}
}
}
void Show()
{
g << sol << '\n';
while(p != -1)
{
g << p << ' ';
p = poz[ p ];
}
}
int main()
{
f >> n;
for(int i = 1; i <= n; ++i)
f >> v[i];
Solve();
Show();
}