Pagini recente » Cod sursa (job #1038607) | Cod sursa (job #1566763) | Cod sursa (job #1367409) | Cod sursa (job #861123) | Cod sursa (job #2574416)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int main(){
ios_base::sync_with_stdio(false);
f.tie(NULL);
int n, maxi = 0, pos = 0;
f >> n;
vector<long> values(n + 1, 0);
vector<int> dp(n + 1, 1);
vector<int> prev(n + 1, -1);
vector<long> res;
for( int i = 0; i < n; i++ ){
f >> values[i];
}
for( int i = 1; i <= n; i++ )
for(int j = 0; j < i; j++){
if( values[i] > values[j] ){
dp[i] = max(dp[i],1 + dp[j]);
if( dp[i] == 1 + dp[j]){
prev[i] = j;
}
}
}
for( int i = 0; i < dp.size(); i++){
if( maxi < dp[i] ){
maxi = dp[i];
pos = i;
}
}
while( prev[pos] != -1 ){
res.push_back(values[pos]);
pos = prev[pos];
}
res.push_back(values[pos]);
g << maxi <<"\n";
for( int i = res.size() - 1; i >= 0; i-- ){
g << res[i] <<" ";
}
}