Pagini recente » Cod sursa (job #2555809) | Cod sursa (job #1941713) | Cod sursa (job #2741727) | Cod sursa (job #1886729) | Cod sursa (job #285051)
Cod sursa(job #285051)
/*
*
* Determina subsirul crescator maximal folosid algoritmul clasic, de complexitate n*n
*
* */
#include <stdio.h>
#define DIM 10001
typedef int Vector[DIM];
FILE *fin=fopen("scm.in","r");
FILE *fout=fopen("scm.out","w");
Vector v, p, l;
int n;
void SCM()
{
int i,j;
l[n]=1, p[n]=-1;
for(i=n-1;i;i--)
{
l[i]=1, p[i]=-1;
for(j=1;j<=n;j++)
if(v[i]<v[j] && l[i]<l[j]+1)
l[i]=l[j]+1, p[i]=j;
}
}
void Afisare()
{
int pmax=1;
for(int i=1;i<=n;i++)
if(l[i]>l[pmax])
pmax=i;
fprintf(fout,"%d\n",l[pmax]);
while(pmax!=-1)
fprintf(fout,"%d ",v[pmax]), pmax=p[pmax];
}
void Citire()
{
fscanf(fin,"%d",&n);
for(int i=1;i<=n;i++)
fscanf(fin,"%d",v+i);
}
int main()
{
Citire();
SCM();
Afisare();
return 0;
}