Mai intai trebuie sa te autentifici.
Cod sursa(job #1998265)
Utilizator | Data | 7 iulie 2017 09:20:06 | |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 20 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.72 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int v[200001];
int secv[200001], poz[200001];
int m, n, plec;
void citire(){
in >> n;
for(int i = 1; i <= n; i++)
in >> v[i];
}
void rezolvare(){
for(int i = n; i >= 1; i--){
secv[i] = 1;
for(int j = i + 1; j <= n; j++){
if(secv[j] + 1 > secv[i] && v[i] < v[j]){
secv[i] = secv[j] + 1;
poz[i] = j;
break ;
}
}
if(m < secv[i]){
m = secv[i];
plec = i;
}
}
out << m << '\n';
for(int i = plec ; i != 0; i = poz[i]){//pana nu termin de sarit pasii : poz[i]
out << v[i] << ' ';
}
}
int main(){
citire();
rezolvare();
return 0;
}