Pagini recente » Cod sursa (job #1305408) | Cod sursa (job #3280055) | Cod sursa (job #2328093) | Cod sursa (job #2825009) | Cod sursa (job #2561315)
#include <fstream>
using namespace std;
ifstream f ("subsir2.in");
ofstream g ("subsir2.out");
int n, v[5005], best[5005];
int sol[5005], aux[5005], lg, k, maxim;
void read ()
{
f >> n;
for (int i=1; i<=n; i++)
f >> v[i], best[i] = 1;
}
void dinamica ()
{
for (int i=2; i<=n; i++)
{
for (int j=1; j<i; j++)
{
if (v[i] > v[j])
{
best[i] = max(best[i], best[j]+1);
maxim = max(maxim, best[i]);
}
}
}
}
void getsubsir (int pozitie)
{
int i, val = best[pozitie];
k = 0;
for (i=pozitie; i>=1; i--)
{
if (val == best[i])
{
k ++, aux[k] = i;
val --;
}
}
}
void compara ()
{
int i;
bool ok = false;
if (lg == 0)
{
for (i=1; i<=k; i++)
{
sol[i] = aux[i];
lg ++;
}
}
else {
for (i=1; i<=k && !ok; i++)
{
if (v[aux[i]] < v[sol[i]])
ok = true;
}
if (ok == true)
{
for (i=1; i<=k; i++)
sol[i] = aux[i];
lg = k;
}
}
}
void solve ()
{
for (int i=1; i<=n; i++)
{
if (best[i] == maxim)
{
getsubsir(i);
compara();
}
}
}
void print ()
{
g << k << '\n';
for (int i=k; i>=1; i--)
g << sol[i] << " ";
}
int main()
{
read();
dinamica();
solve();
print();
return 0;
}