# longest increasing subsequence

**Longest increasing subsequence problem: Dynamic programing**

**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 and its length.*

*An un-optimize solution:*

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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#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; } |

## Leave a Reply