Nu aveti permisiuni pentru a descarca fisierul grader_test10.ok
Cod sursa(job #1325756)
Utilizator | Vali Deaconu Vali_Deaconu | Data | 24 ianuarie 2015 12:33:28 |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 70 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.93 kb |
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
int v[100010];
int n;
int i, j;
int L[100010];
int maxim, M;
int t[100010];
int p, u;
int sol[100010];
int k;
int main()
{
fin >> n;
for (i=1; i<=n; ++i) {
fin >> v[i];
}
L[1] = 1;
t[1] = 0;
M = 1;
for (i=2; i<=n; ++i) {
maxim = 0;
for (j=1; j<i; ++j)
if ((L[j] > maxim) && (v[j] < v[i])) {
maxim = L[j];
p = j;
}
L[i] = 1 + maxim;
if (maxim == 0)
t[i] = 0;
else
t[i] = p;
if (L[i] > M) {
M = L[i];
u = i;
}
}
fout << M << "\n";
while (u != 0) {
sol[++k] = v[u];
u = t[u];
}
for (i=M;i>=1;i--)
fout<<sol[i]<<" ";
return 0;
}