Question

Bună seara Family!!
Sunt Clasa 11 MII
Îmi trebuie neapărat în seara asta.
Dacă știți sa rezolvați aceasta problema va ofer cele 35 de puncte și o coroană!
Vreau să-mi scrieți programul în C++ și dacă se mai poate să-mi și explicații rezolvarea problemei.
Va mulțumesc pentru ajutor.
O seara faina!!


Se dă un șir cu n elemente, numere naturale. Determinați un cel mai lung subșir crescător al șirului.

De exemplu, pentru n=10 și șirul A=(5, 10, 7, 4, 5, 8, 9, 8, 10, 2), cel mai lung subșir crescător va conține 5 elemente (5, 7, 8, 9, 10) sau (4, 5, 8, 9, 10).

​

Answer 1

Răspuns:

#include <iostream>

using namespace std;

int v[10000],n,i,L[1000],maxim,mx,k,t;

int main()

{cout<<"Cel mai lung subsir crescator"<<endl;

cout<<"n="; cin>>n;

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

{cout<<"v["<<i<<"]=";

cin>>v[i];}

L[n]=1; //subsir maxim de lung 1

for(k=n-1;k>0;k--)

{mx=0;

for(i=k+1;i<=n;i++)

if(v[i]>=v[k] && L[i]>mx) mx=L[i];

L[k]=mx+1;

if(L[k]>maxim) {maxim=L[k]; t=k;} }

cout<<"lungimea maxima:"<<maxim; //afisarea subsirului

cout<<endl<<v[t]<<' ';

for(i=t+1;i<=n;i++)

if ((v[i]>=v[t]) && (L[i]==maxim-1))

{cout<<v[i]<<' '; maxim--;}

return 0;

}

O aveam facută de la clasă, nu mă pricep neapărat să explic. Sper să te ajute tho :)