Longest increasing subsequence problem: Dynamic programing

Given a set of integers in unsorted manner find the length of longest increasing subsequence. for example 10 23 3 45 56 24 80 25 98 longest increasing subsequence is 10 23 45 56 80 98 and its length is 6. then write an efficient c program to to find longest increasing subsequence’s length.

A[] = { 10 23 3 45 56 24 80 25 98 }

Following is a solution with O(n^2) complexity using Dynamic Programming.

#include <iostream>
using namespace std;

int lis(int *arr, int n) {
	// create a new array
	int *s = new int[n];
	int mx = -1000;

	// init s with default value 1
	for (int i = 0; i < n; i++)
		s[i] = 1;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j] && s[i] <= s[j]) {
				s[i]++;
			}
		}
		if (s[i] > mx)
			mx = s[i];
	}
	// return max
	return mx;
}

int main() {
	int arr[] = { 10, 23, 3, 45, 56, 24, 80, 25, 98 };
	cout << lis(arr, sizeof(arr)/sizeof(int));
	return 0;
}

 




Related Contents to follow