Pagini recente » Cod sursa (job #2275214) | Cod sursa (job #307512) | Cod sursa (job #2723618) | Cod sursa (job #1525766) | Cod sursa (job #2005603)
// facem varianta de 70 de pt cu programare dinamica.
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n, i, j, nr, v[100003], in, x, best[100003], pre[100003], mx;
deque <int> dq;
int main () {
fin >> n;
for (i = 1; i <= n; i++)
fin >> v[i];
best[1]=1;
bool ok = 0;
for (i = 2; i <= n; i++)
{
mx = 0;
ok = 0;
for (j = 1; j < i; j++)
if (v[j] < v[i] && best[j] > mx)
{
mx = best[j];
pre[i] = j;
ok = 1;
}
if (ok == 1) best[i] = mx + 1;
else best[i] = 1;
}
/*for (i = 1; i <= n; i++)
cout << best[i] << " ";
cout << "\n";
for (i = 1; i <= n; i++)
cout << pre[i] << " ";*/
mx = 0;
for (i = 1; i <= n; i++)
if (best[i] > mx)
{ mx = best[i]; in = i; }
dq.push_back(v[in]);
while (v[in] != 0)
{
in = pre[in];
if (v[in] != 0) dq.push_front(v[in]);
}
fout << mx << "\n";
for (i = 0; i < dq.size(); i++)
fout << dq[i] << " ";
}