C.M.L.S.C.

Enunț:

Se consideră un șir v oarecare de n element numere întregi, v1,v2,…,vn. Se cere să se determine cel mai lung subșir ordonat crescător (CMLSC) al șirului.

Indicație de rezolvare:

Pentru a calcula lungimea celui mai lung subșir ordonat crescător (CMLSC), vom calcula mai întâi lungimile celor mai lungi subșiruri crescătoare care încep cu fiecare element al vectorului. Vom memora în L[k] lungimea CMLSC care începe de la poziția k și până la sfârșitul șirului inițial. Tabloul unidimensional L are n elemente. Pentru ultimul element, L[n – 1] = 1. Calculăm apoi pe rând L[n – 2], …, L[1], L[0]. Lungimea CMLSC va fi dată de cea mai mare valoare a vectorului L.

Vrem să calculăm L[k]. Pentru aceasta, trebuie mai întâi să calculăm lungimea CMLSC din dreapta lui k, subșir al cărui prim element este mai mare sau egal cu elementul de pe poziția k. Dar această lungime o putem determina în același mod. Obținem următoarea formulă de recurență.

Pentru a afișa și elementele CMLSC, folosim un vector suplimentar, next, în care reținem pe poziția k indexul primului element al subșirului folosit pentru calcularea lui L[k].

Implementare:

Cod Sursa C++

// CMLSC.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
 
using namespace std;
 
void CMLSC(int *v, int n)
{
	int Lmax, start, i, k;
	int *L = new int[n];
	int *next = new int[n];
	L[n - 1] = 1;
	Lmax = 1;
	start = n - 1;
	next[n - 1] = n - 1;
	for (k = n - 2; k >= 0; k--)
	{
		L[k] = 1;
		next[k] = k;
		for (i = k + 1; i < n;i++)
		if (v[k] <= v[i] && L[k] <= L[i])
		{
			L[k] = L[i] + 1;
			next[k] = i;
		}
		if (L[k]>Lmax)
		{
			Lmax = L[k];
			start = k; //pozitia de inceput a subsirului
		}
	}
	cout << "Lungimea CMLSC: " << Lmax << endl;
	cout << "Aceasta este: " << v[start] << " ";
	for (i = 1; i < Lmax; i++)
	{
		start = next[start];
		cout << v[start] << " ";
	}
	cout << endl;
	delete L;
	delete next;
}
 
int main()
{
	int n, *v;
	cout << "Lungimea sirului: ";
	cin >> n;
	v = new int[n];
	cout << "Elementele sirului: ";
	for (int i = 0; i < n; i++)
	{
		cout << "v[" << i << "]=";
		cin >> v[i];
	}
	CMLSC(v, n);
	system("pause");
}
 

 Rezultat: