No. 16 – Maximal Length of Incremental Subsequences

Problem: Given an unsorted array, find the max length of subsequence in which the numbers are in incremental order.

For example: If the input array is {7, 2, 3, 1, 5, 8, 9, 6}, a subsequence with the most numbers in incremental order is {2, 3, 5, 8, 9} and the expected output is 5.

Reference: http://codercareer.blogspot.com/2011/10/no-16-maximum-length-of-incremental.html

/* Copyleft: Ming Lin <minggr@gmail.com> */

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

int maximal(int data[], int n)
{
	int *max;
	int i, j;
	int m, r;
	int cur;

	max = malloc(sizeof(int)*n);

	r = -1;
	max[0] = 1;
	for (i = 1; i < n; i++) {
		m = -1;
		for (j = 0; j < i; j++) {
			if (data[i] > data[j]) {
				cur = max[j] + 1;
			} else
				cur = 1;
			if (m == -1 || cur > m)
				m = cur;
		}
		max[i] = m;

		if (r == -1 || max[i] > r)
			r = max[i];
	}

	free(max);
	return r;
}

int main()
{
	int data[] = {7,2,3,1,5,8,9,6};
	int n = 8;

	printf("%d\n", maximal(data, n));

	return 0;
}

 

Leave a Reply