The longest substring ascending – algorithm

    We will use the term to mean that a painting long [i] = length the longest substring starting position ascending i.If the string of length n items are in vector 0 starting position we have:
long [n-1] = 1
long [i] = max {1.1 + max {long [j] | of <= aj}}, 0 <= i <= n-1
If the longest substring starting position and the greater of increasing subsequences start position j (j> i) and accepting adding to the first element of (ai <= aj) .To be able to restore
and we used vector sequence elements WHERE WHERE where [i] = position where the next element of the ascending part of substring you.

If WHERE [i] = i then the item is part of a subsequence ascending consisting only of himself.

/*Vom utiliza  un tablou lung cu semnificatia ca lung[i] = lungimea
celui mai lung subsir crescator care incepe pe pozitia i.Daca pre-
supunem ca elementele sirului de lungime n se afla in vectorul a 
incepand cu pozitia 0 vom avea:
lung[n-1] = 1
lung[i] = max{1,1+max{lung[j]|ai<=aj}},0<=i<=n-1
adica cel mai lung subsir care incepe pe pozitia i este maximul dintre
subsirurile crescatoare care incep pe pozitia j (j>i) si care accepta
adaugarea la inceput a elementului ai(ai<=aj).Pentru a putea reconstitui
si elementele secventei am utilizat vectorul where unde where[i] = pozitia
unde se afla urmatorul element al subsirului crescator din care face parte
ai. Daca where[i] = i atunci elementul ai face parte dintr-un subsir crescator 
format doar din el insusi.*/

#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <stdlib.h>

/*se aloca un bloc de n numere intregi daca nu se poate aloca atunci se 
opreste executia programului cu un mesaj de eroare*/
int* aloc(int n)
{
	int* tab;
	tab = (int*) malloc(n*sizeof(int));

	if(tab == NULL)
	{
		printf("Memorie insuficienta! \n");
		exit(1);
	}
	return tab;
}

/*se citeste nr de elemente n si elementele numere intregi*/
int read_data(int **tab)
{
	int i,n;

	printf("n=");scanf("%d",&n);

	*tab = aloc(n);
	for(i=0;i<n;i++)
	{
		printf("number[%d] = ",i);
		scanf("%d",&((*tab)[i]));
	}
	return n;
}

void run(int* a,int n)
{
	int i,j;
	int max_sir = 0;
	int position = 0;
	int *lung;
	int *wheres;

	lung = aloc(n);
	wheres = aloc(n);

	lung[n-1] = 1;
	wheres[n-1] = n-1;
	for(i=n-2;i>=0;i--)
	{
		lung[i] = 1;
		wheres[i] = i;
		for(j=i+1;j<n;j++)

			if(a[i] <= a[j] && lung[i] < lung[j] + 1)
			{
				lung[i] = lung[j] + 1;
				wheres[i] = j;
			}
			if(max_sir < lung[i])
			{
				max_sir = lung[i];
				position = i;
			}
	}

	printf("Subsirul de lungime: %d \n",max_sir);
	i = position;
	while(i != wheres[i])
	{
		printf("%2d ",a[i]);
		i = wheres[i];
	}
	printf("%2d\n",a[i]);

	free(lung);
	free(wheres);
	free(a);
}

void main()
{
	int *a;
	int n = read_data(&a);

	run(a,n);
}

746,317 total views, 1 views today