Subsir Crescator Maximal

15/11/2010 § Leave a comment

-enunt:

Se citeste de la tastatura n, un numar natural si un vector v cu n elemente naturale. Afisati cel mai lung subsir de numere din vectorul v ordonat crescator si lungimea acestuia.

D.I. :  Fisierul “subsir.in” contine pe prima linie n iar pe urmatoarea linie n numere naturale.

D.O.:  Fisierul “subsir.out” va contine pe prima linie lungimea maxima a sirului si pe urmatoarea linie elementele sirului.

-exemplu:

subsir.in

7
3 6 9 2 5 11 45

subsir.out

Lungimea maxima este 5

3 6 9 11 45

-program:

#include<iostream.h>
#include<fstream.h>
int n,v[100],d[100],p[100];
ofstream g(“subsir.out”);
void citire()
{
int i;
ifstream f(“subsir.in”);
f>>n;
for(i=1;i<=n;i++)
f>>v[i];
f.close();
}
void afisare(int k)
{
while(k!=0)
{
g<<v[k]<<” “;
k=p[k];
}
}
void dinamita()
{
int i,j,poz,pozm,maxp,max;
d[n]=1;
p[n]=0;
pozm=n;
maxp=1;
for(i=n-1;i>=1;i–)
{
max=0;
poz=-1;
for(j=i+1;j<=n;j++)
if(v[j]>v[i] && d[j]>max)
{
max=d[j];
poz=j;
}
if(poz==-1)
{
d[i]=1;
p[i]=0;
}
else
{
d[i]=1+d[poz];
p[i]=poz;
if(d[i]>maxp)
{
maxp=d[i];
pozm=i;
}
}
}
g<<maxp<<“\n”;
afisare(pozm);
}
int main()
{
citire();
dinamita();
return 0;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

What’s this?

You are currently reading Subsir Crescator Maximal at crengux.

meta

%d bloggers like this: