Skip to content

Instantly share code, notes, and snippets.

@krisys
Last active October 12, 2015 21:28
Show Gist options
  • Save krisys/4089697 to your computer and use it in GitHub Desktop.
Save krisys/4089697 to your computer and use it in GitHub Desktop.
Longest Increasing sequence
#include <iostream>
#include <algorithm>
using namespace std;
int a[] = {4, 3, 1 ,2, 8, 3, 4};
// int a[] = {1, 6, 2 ,3, 4, 5, 7};
// int a[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
// int a[] = {5,4,6,3,7};
int N = sizeof(a)/sizeof(a[0]);
int dp[50] = {1};
int main(){
/*
We should search for longest increasing subsequence(LIS) with K elements first,
then it can be extended to (K + 1)th element. So we build a table with lengths
of longest sequences for each index till K. When we have the (K + 1)th element,
we should try to search for an element in the previous K elements which can
be the predecessor to this element.
From the data set : {4, 3, 1 ,2, 8, 3, 4}
E [L] - Element, and length of longest increasing subsequence.
4 [1] - It is the only element so far, so we have the length of LIS as 1
3 [1] - If we observe, the previous number is 4 which is greater than the current.
So we cannot reach 3 from 4. so the length is still 1.
1 [1] - Same in this case.. 3 is larger than 1. so the length of LIS is still 1.
2 [2] - If we scan the numbers before 2, we find 1, a number which can be a
predecessor to 2. So we increment the length from 1 to 2 (dp[i] = dp[j] + 1).
8 [3] - We see that, we can reach 8 from 2. So, we increase the length from 2 to 3.
3 [3] - Again, we can reach 3 from 2. So, we pick 2 as the predecessor.
4 [4] - We can reach 4 from 3. So we incremenet the length once again.
*/
int ans = 1;
for(int i=1;i<N;i++){
dp[i] = 1;
for(int j = i - 1 ; j >= 0; j--){
if(a[j] < a[i]){
dp[i] = max(dp[i], dp[j] + 1);
}
ans = max(ans, dp[i]);
}
}
cout << ans << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment