Pagini recente » Cod sursa (job #2653517) | Cod sursa (job #431111) | Cod sursa (job #1860109) | Cod sursa (job #547221) | Cod sursa (job #978938)
Cod sursa(job #978938)
#include <fstream>
using namespace std;
int n, i, k, v[100000], lg[100000], p, maxi;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int main() {
fin >> n;
for (i = 0; i < n; i++)
fin >> v[i];
fin.close();
//dinamica
lg[n - 1] = 1;
for (k = n - 2; k >= 0; k--) {
maxi = 0;
for (i = k + 1; i < n; i++)
if (v[k] < v[i] and lg[i] > maxi)
maxi = lg[i];
lg[k] = 1 + maxi;
}
// for (i = 0; i < n; i++)
// fout << v[i] << ' ';
// fout << '\n';
// for (i = 0; i < n; i++)
// fout << lg[i] << ' ';
// fout << '\n';
// o posibila varianta
maxi = lg[0]; p = 0;
// cautam primul maxim
for (i = 1; i < n; i++)
if (lg[i] > maxi) {
maxi = lg[i]; p = i;
}
fout << maxi << '\n';
fout << v[p] << ' ';
for (i = p + 1; i < n; i++)
if (v[p] <= v[i] and lg[i] == maxi - 1) {
fout << v[i] << ' '; maxi--;
}
fout.close();
return 0;
}