Cod sursa(job #2309051)

Utilizator _Victor_Victor Ciobanu _Victor_ Data 28 decembrie 2018 13:14:39
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.55 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n,sol=0,A[100001],S[100001],DP[2][100001],ind;

int main(){
	fin>>n;
	for(int i=0;i<n;i++){
		fin>>A[i];
		DP[0][i]=1;
		DP[1][i]=0;
		for(int j=0;j<i;j++){
			if(A[i]>A[j] && DP[0][i]<DP[0][j]+1){
				DP[0][i]=DP[0][j]+1;
				DP[1][i]=j;
			}
		}
		if(sol<DP[0][i]){
			sol=DP[0][i];
			ind=i;
		}
	}
	fout<<sol<<'\n';
	for(int i=sol-1;i>=0;i--){
		S[i]=A[ind];
		ind=DP[1][ind];
	}
	for(int i=0;i<sol;i++)fout<<S[i]<<' ';
}