infoooo…

Subsir crescator maximal

Se da un vector v[] cu n elemente numere intregi.

Afisati lungimea celui mai lung subsir crescator.

#include<iostream.h>

int v[100], d[100], poz[100], n;

void citire()

{  int i;

cin>>n;

for(i=1; i<=n; i++) cin>>v[i];

}

void dinamica()

{ int i, j, max, p;

d[n]=1; poz[n]=0;

for(i=n-1; i>=1; i–)

{ max=0; p=0;

for(j=i+1; j<=n; j++)   if(v[i]<v[j] && d[j]>max)  {max=d[j]; p=j; }

d[i]=max+1; poz[i]=p }

p=1;

for(i=2; i<=n; i++)

if(d[i]>d[p])  p=i;

cout<<d[p];

while(p!=0)

{cout<<v[p]; p=poz[p]; }

}

int main()
{ citire();

dinamica();

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