Cod sursa(job #1496288)

Utilizator andreyi424Andrei Badoi andreyi424 Data 4 octombrie 2015 18:19:55
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream gout("scmax.out");
void scmax(int a[],int n)
{
	int *sub = new int [n], maxim = 0;
	for(int i=0;i<n;i++)
		sub[i] = 0;
	sub[n-1] = 1;
	for (int i=n-2;i>=0;--i)
	{
		int mx = 0;
		for(int j = i+1;j<n;j++)
			if(a[i]<a[j])
				mx = max(mx,sub[j]);
		sub[i] = mx + 1;
		maxim = max(sub[i],maxim);
	}
	gout << maxim <<endl;
	for (int i = 0;i<n;i++)
		if(sub[i] == maxim){
			gout << a[i] <<" ";
			maxim--;
		}
}
int main()
{
 
 
    int n,*a;
    fin>>n;
    a = new int[n];
    for(int i=0;i<n;++i)
        fin>>a[i];
    scmax(a,n);
    return 0;


}