Cod sursa(job #3142522)

Utilizator andrei_botorogeanuBotorogeanu Andrei andrei_botorogeanu Data 22 iulie 2023 09:14:17
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include<fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n, v[100001], l[100001];
int max_l, poz_max;
void dynamic_programming()
{
	l[n]=1;
	int best_max;
	for(int j=n-1; j>=1; j--)
	{
		best_max=0;//
		for(int k=j+1; k<=n; k++)//
		{
			if( v[k] > v[j] && l[k]>best_max )
				best_max = l[k];	
		}
		l[j]=1+best_max;
	}
	// cout<<endl;
	// for(int i=1; i<=n; i++)
	// 	cout<< l[i]<< " ";
	for(int w=1; w<=n; w++)
		if(l[w] > max_l)	
		{
			max_l=l[w];
			poz_max=w;
		}
		fout<<max_l<<endl;
		fout<<v[poz_max]<< " ";
	for(int i=poz_max+1; i<=n; i++)
	{
		if( v[i] > v[poz_max] && l[i]==max_l-1 )
		{
			fout << v[i] << " ";
			max_l--;
		}
	}	
	// Vectorul l este folosit ca sa masoare lungimea maxima 
	// a subsirului crescator incepand de la un anumit index (i)

//l[  5  ] = 9 -> inseamna ca de la indexul 5 lung. sirului maximal este 9 componente 
//  index    nr maxim de componente ale subsirului crescator 

// ex: 56 67 89 45  2 54
//	l: 1  2  1  1  2  1
// 	poz_max=1;
// 	v[poz_max]=56;
}
int main()
{
	fin>>n;
	for(int i=1; i<=n; i++)
		fin>>v[i];
	dynamic_programming();
}