Cod sursa(job #2452720)
Utilizator | Data | 31 august 2019 23:05:04 | |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 10 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.61 kb |
#include <fstream>
#include <iostream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int v[100005], dp[100005], pre[100005], n;
void afisSubsir(int n) {
if(pre[n])
afisSubsir(pre[n]);
g << v[n] << ' ';
}
int main() {
f >> n;
for(int i = 1; i <= n; i++)
f >> v[i];
for(int i = 1; i <= n; i++) {
dp[i] = 1;
for(int j = 1; j < i; j++)
if(v[j] < v[i] && dp[j]+1 > dp[i]) {
dp[i] = dp[j]+1;
pre[i] = j;
}
}
g << dp[n] << '\n';
afisSubsir(n);
}