Pagini recente » Cod sursa (job #3171648) | Cod sursa (job #2289369) | Cod sursa (job #2001717) | Cod sursa (job #1664219) | Cod sursa (job #2868851)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int cap[100002], ult[100002], a[100002], len[100002], n;
int nr_siruri, poz[100002];
/**
cap[i] - elementele din fiecare subsir nou creat
Recurenta:
dp[i] = 1 + max(dp[1]...dp[i - 1])
poz[i] - pozitia valorii care
*/
void Citire()
{
int i, j, x, maxx;
bool flag;
fin >> n;
for (i = 1; i <= n; i++)
{
fin >> a[i];
}
cap[1] = a[1];
nr_siruri = 1;
poz[1] = 1;
len[1]++;
for (i = 2; i <= n; i++)
{
maxx = 0;
flag = false;
for (j = 1; j <= nr_siruri; j++)
{
if (cap[j] < a[i] && maxx < cap[j])
{
maxx = cap[j];
poz[i] = j;
flag = true;
}
}
if (flag == false)
{
nr_siruri++;
cap[nr_siruri] = a[i];
len[nr_siruri]++;
poz[i] = nr_siruri;
}
else
{
cap[poz[i]]++;
len[poz[i]]++;
cap[poz[i]] = a[i];
}
}
maxx = 0;
for (i = 1; i <= nr_siruri; i++)
{
if (maxx < len[i])
{
maxx = len[i];
x = i;
}
}
fout << maxx << '\n';
for (i = 1; i <= n; i++)
{
if (poz[i] == x)
fout << a[i] << ' ';
}
}
int main()
{
Citire();
fin.close();
fout.close();
return 0;
}