Pagini recente » Istoria paginii utilizator/vvvlll50 | Rating Vasile Dan (danezu55) | Cod sursa (job #566366) | Cod sursa (job #1081718) | Cod sursa (job #16077)
Cod sursa(job #16077)
#include<stdio.h>
#define max 5001
#define input "subsir2.in"
#define output "subsir2.out"
long LMAX, lmax, pozitia, lung[max], a[max], cont[max], j, v[max], k, n, minim,expandat[max];
void Citire();
void Rezolva();
void Scrie();
int main()
{
Citire();
Rezolva();
Scrie();
return 0;
}
void Citire()
{
FILE *in;
long i;
in = fopen ( input, "r");
fscanf(in, "%ld", &n);
for(i=1; i<=n; i++)
fscanf(in, "%ld", &a[i]);
}
void Rezolva()
{
long i;
lung[1]=1;
cont[1]=0;
for(i=2; i<=n; i++)
{
lmax=0;
lung[i]=1;
cont[i]=0;
for(j=i-1; j; j--)
if(a[i]>=a[j])
{
if( lmax<lung[j])
{
lmax=lung[j];
minim=j;
}
else
if((lmax==lung[j])&&(a[minim]>a[j]))
minim=j;
expandat[j] = 1;
}
if(lmax)
{
lung[i]=lmax+1;
cont[i]=minim;
}
}
for(i=1; i<=n; i++)
if(!expandat[i])
if(lung[i]>LMAX)
{
LMAX=lung[i];
pozitia=i;
}
else if((lung[i]==LMAX) && a[i]<a[pozitia])
pozitia =i;
}
void Scrie()
{
FILE *out;
out = fopen (output, "w");
fprintf(out, "%ld\n", LMAX);
int i=pozitia;
k=0;
while(i)
{
v[++k]=i;
i=cont[i];
}
for(i=k; i; i--)
fprintf(out, "%ld ", v[i]);
}