Cod sursa(job #2177436)

Utilizator DarinelaAndronovici Darinela Darinela Data 18 martie 2018 16:32:26
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
unsigned long long A[200000000], B[200000000], C[200000000], D[200000000], i,p,n,j;

int main(){
	fin>>n;
	for (i=1; i<=n; i++){
							fin>>A[i];		
	}
   C[n]=1;
    D[n]=0;
	for (i=n-1; i>=1; i--)
	{
		p=i;
		C[i]=0;
		for(j=i+1; j<=n; j++)
		{
			if ((A[i]<A[j]) && (C[j]>C[p]))
			p=j;
		}
			C[i]=C[p]+1;
			if(p!=i){
			
				D[i]=p;
			}
			else D[i]=0;
		}
	p=n;	
	for (i=n-1; i>=1; i--)
	          if(C[i]>C[p]) p=i;
    fout<<C[p]<<endl;
    fout<<A[p]<<" ";
    p=D[p];
    while (p) {
    	fout<<A[p]<<" ";
    	p=D[p];
	}
return 0;
}