Pagini recente » Cod sursa (job #1823999) | Cod sursa (job #1310182) | Cod sursa (job #929273) | Cod sursa (job #2722965) | Cod sursa (job #2462447)
#include <fstream>
#define Nmax 100000
using namespace std;
void citire(int &n, int x[])
{ifstream in("scmax.in");
in>>n;
for(int i=0; i<n; i++)
in>>x[i];
in.close();
}
void subsir_crescator(int n, int x[],int &lS, int s[])
{/*Functia determina cel mai lung subsir crescator al sirului x*/
int L[Nmax];/*L[i] = lungimea unui subsir maxim cu capatul in i */
int lM=0,pM=0;/*lungimea subsirului si pozitia capatului*/
int capat=0;/*valoarea ultimului element din subsir*/
for(int i=0; i<n; i++)
{
L[i] = 0;
for(int j=0; j<i; j++)
if(x[j]<x[i] and L[j]>L[i])
L[i] = L[j];
L[i]+=1;/*adaugam si capatul*/
if(L[i]>lM)
{
lM = L[i];
pM = i;
capat = x[i];
}
}
/*Construim subsirul*/
s[lS] = capat; lS=1;
for(int i=pM-1; i>=0; i--)
if(x[i]<capat and L[i]==lM-1)
{
s[lS] = x[i]; lS++;
capat = x[i]; lM--;
}
}
void afisare(int lS, int s[])
{ofstream out("scmax.out");
out<<lS<<'\n';
for(int i=lS-1; i>=0; i--)
out<<s[i]<<" ";
out.close();
}
int main()
{
int n, x[Nmax];
citire(n,x);
int lS=0, s[Nmax];/*subsirul crescator*/
subsir_crescator(n,x,lS,s);
afisare(lS,s);
return 0;
}