Pagini recente » Cod sursa (job #372284) | Ciorna | Cod sursa (job #3210180) | infoexpert | Cod sursa (job #3258051)
#include <fstream>
#include <vector>
using namespace std;
void refac_subsirul(ofstream &out, vector <int> &v, vector <int> &lung, int p, int lg, int val)
{
///cautam incepand la stanga poz. p elem. <= val, cu subsirul de lungime lg
if (p < 0)
{
return;
}
if (v[p] <= val && lung[p] == lg)
{
refac_subsirul(out, v, lung, p - 1, lg - 1, v[p] - 1);
out << v[p] << " ";
}
else
{
refac_subsirul(out, v, lung, p - 1, lg, val);
}
}
int main()
{
ifstream in("scmax.in");
ofstream out("scmax.out");
int n, ultimul = 0;
in >> n;
vector <int> v(n), lung(n);
for (int i = 0; i < n; i++)
{
in >> v[i];
int lmax_i = 0;
for (int j = 0; j < i; j++)
{
if (v[j] < v[i])
{
lmax_i = max(lmax_i, lung[j]);
}
}
lung[i] = 1 + lmax_i;
if (lung[i] > lung[ultimul])
{
ultimul = i;
}
}
out << lung[ultimul] << "\n";
refac_subsirul(out, v, lung, ultimul, lung[ultimul], v[ultimul]);
in.close();
out.close();
return 0;
}