Pagini recente » Istoria paginii runda/acsdfg | Cod sursa (job #2041459) | Cod sursa (job #2783510) | Cod sursa (job #1871210) | Cod sursa (job #809004)
Cod sursa(job #809004)
#include <fstream>
using namespace std;
ifstream intrare("scmax.in");
ofstream iesire("scmax.out");
int n;
int v[100000];
int lgmax[100000], urm[100000];
int mmax, ind;
int main()
{
int i, j;
intrare >> n;
for(i = 0; i < n; i++)
intrare >> v[i];
lgmax[n-1] = 1;
urm[n-1] = -1;
for(i = n - 2; i >= 0; i--)
{
lgmax[i] = 1;
urm[i] = -1;
for(j = i + 1; j < n; j++)
if (lgmax[i] < 1 + lgmax[j] && v[i] < v[j])
{
lgmax[i] = 1 + lgmax[j];
urm[i] = j;
}
}
for(i = 0; i < n; i++)
if (lgmax[i] > mmax)
{
mmax = lgmax[i];
ind = i;
}
iesire << mmax << '\n';
for(i = 0; i < mmax; i++)
{
iesire << v[ind] << " ";
ind = urm[ind];
}
iesire << '\n';
iesire.close();
return 0;
}