Cod sursa(job #2574399)

Utilizator lucian2015blaugranadevil lucian2015 Data 5 martie 2020 22:03:08
Problema Subsir crescator maximal Scor 45
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#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] <<" ";
 }
}