Subsir Crescator Maximal

-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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s