Pagini recente » Cod sursa (job #461850) | Cod sursa (job #994361) | Cod sursa (job #1865542) | Cod sursa (job #457623) | Cod sursa (job #2574399)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int main(){
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]);
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] <<" ";
}
}