Pagini recente » Cod sursa (job #1280999) | Cod sursa (job #1090822) | Cod sursa (job #623132) | Cod sursa (job #3215382) | Cod sursa (job #3142522)
#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();
}