Problem
Longest Increasing Subsequence of given sequence with best time complexity
ex:
Input [6, 20, 5, 31, 19, 49, 39, 58, 79]
Output : is [6, 20, 31, 49, 58, 79]
Solution
Using dynamic programming
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find longest increasing subsequence
Created Date : 01-August-2013
Last Modified : 02-August-2013
===========================================================================
*/
#include <iostream>
#include <iomanip>
#include <iterator>
#include <vector>
using namespace std;
int FindLongestSubseq(vector<int>& input)
{
vector<int> lens(input.size());
lens.assign(input.size(), 1);
int maxLen(1);
int index(0);
for(int i = input.size() - 1; i >= 0; --i){
int m = 1;
for(int j = i + 1; j < input.size(); ++j){
int n = (input[i] < input[j]) ? lens[j] + 1 : 1;
m = max(m, n);
}
if(m > maxLen){
maxLen = m;
index = i;
}
lens[i] = m;
}
cout << "The index start from " << index << endl;
cout << "The longest subSequence is " << endl;
int m = maxLen - 1;
int prev = input[index];
cout << setw(4) << prev;
for(int i = index + 1; i < input.size() && m > 0; ++i){
if(lens[i] == m && prev < input[i]){
cout << setw(4) << input[i];
prev = input[i];
m --;
}
}
cout << endl;
return maxLen;
}
void DoTest(vector<int>& input)
{
cout << "The input is " << endl;
copy(input.begin(), input.end(), ostream_iterator<int>(cout, " "));
cout << endl;
int len = FindLongestSubseq(input);
cout << "\nThe size of longest subsequence is " ;
cout << len << endl;
cout << "----------------------" << endl;
}
int main(int argc, char* argv[])
{
int arr0[] = {6, 20, 5, 31, 19, 49, 39, 58, 79};
vector<int> v0(arr0, arr0 + sizeof(arr0)/sizeof(int));
DoTest(v0);
int arr1[] = {27, 6, 20, 5, 31, 19, 49, 39, 58, 79};
vector<int> v1(arr1, arr1 + sizeof(arr1)/sizeof(int));
DoTest(v1);
int arr2[] = {3, 5, 2, 8, 6, 3, 6, 9, 7, 5};
vector<int> v2(arr2, arr2 + sizeof(arr2)/sizeof(int));
DoTest(v2);
int arr3[] = {3};
vector<int> v3(arr3, arr3 + sizeof(arr3)/sizeof(int));
DoTest(v3);
int arr4[] = {3, 5};
vector<int> v4(arr4, arr4 + sizeof(arr4)/sizeof(int));
DoTest(v4);
int arr5[] = {5, 3};
vector<int> v5(arr5, arr5 + sizeof(arr5)/sizeof(int));
DoTest(v5);
int arr6[] = {5, 4, 3, 2, 1};
vector<int> v6(arr6, arr6 + sizeof(arr6)/sizeof(int));
DoTest(v6);
int arr7[] = {1, 2, 3, 4, 5};
vector<int> v7(arr7, arr7 + sizeof(arr7)/sizeof(int));
DoTest(v7);
return 0;
}
Output
The input is
6 20 5 31 19 49 39 58 79
The index start from 0
The longest subSequence is
6 20 31 49 58 79
The size of longest subsequence is 6
----------------------
The input is
27 6 20 5 31 19 49 39 58 79
The index start from 1
The longest subSequence is
6 20 31 49 58 79
The size of longest subsequence is 6
----------------------
The input is
3 5 2 8 6 3 6 9 7 5
The index start from 2
The longest subSequence is
2 3 6 9
The size of longest subsequence is 4
----------------------
The input is
3
The index start from 0
The longest subSequence is
3
The size of longest subsequence is 1
----------------------
The input is
3 5
The index start from 0
The longest subSequence is
3 5
The size of longest subsequence is 2
----------------------
The input is
5 3
The index start from 0
The longest subSequence is
5
The size of longest subsequence is 1
----------------------
The input is
5 4 3 2 1
The index start from 0
The longest subSequence is
5
The size of longest subsequence is 1
----------------------
The input is
1 2 3 4 5
The index start from 0
The longest subSequence is
1 2 3 4 5
The size of longest subsequence is 5
----------------------
Press any key to continue . . .