Dynamic Programming: Longest Increasing Subsequence
In this post, I'm going to talk about a short but interesting example where dynamic programming is useful.
The problem: Find the length of the longest strictly increasing subsequence. (Note: Subsequences, unlike substrings, do not have to be contiguous! Also, multiple subsequences may have the max length.)
For example, in {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}, the length of the LIS is 6, and the three possible LIS's are {0, 2, 6, 9, 11, 15}, {0, 4, 6, 9, 11, 15}, and {0, 4, 6, 9, 13, 15}.
The approach: Let's call L(i) the length of the LIS contained in the indices 0 through i. To reduce L(i), we need to consider all the elements at indices 0 through i-1. Then, L(i) is equal to 1 plus the maximum L(j), where j is between 0 and i-1, and the jth element is smaller than the ith element.
This algorithm is O(n^2). My code for the dynamic programming approach to this problem is below...
static int[] tab;
public static int lis(int[] a) {
tab[0] = 1;
for(int i = 1; i < a.length; i++) {
int maxlen = Integer.MIN_VALUE;
for(int j = 0; j < i; j++)
if(a[i] > a[j] && tab[j] > maxlen)
maxlen = tab[j];
tab[i] = 1 + maxlen;
}
return tab[a.length-1];
}
All my code is on Github - try running it yourself!
Source(s): Wikipedia, Clemson
The problem: Find the length of the longest strictly increasing subsequence. (Note: Subsequences, unlike substrings, do not have to be contiguous! Also, multiple subsequences may have the max length.)
For example, in {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}, the length of the LIS is 6, and the three possible LIS's are {0, 2, 6, 9, 11, 15}, {0, 4, 6, 9, 11, 15}, and {0, 4, 6, 9, 13, 15}.
The approach: Let's call L(i) the length of the LIS contained in the indices 0 through i. To reduce L(i), we need to consider all the elements at indices 0 through i-1. Then, L(i) is equal to 1 plus the maximum L(j), where j is between 0 and i-1, and the jth element is smaller than the ith element.
This algorithm is O(n^2). My code for the dynamic programming approach to this problem is below...
static int[] tab;
public static int lis(int[] a) {
tab[0] = 1;
for(int i = 1; i < a.length; i++) {
int maxlen = Integer.MIN_VALUE;
for(int j = 0; j < i; j++)
if(a[i] > a[j] && tab[j] > maxlen)
maxlen = tab[j];
tab[i] = 1 + maxlen;
}
return tab[a.length-1];
}
All my code is on Github - try running it yourself!
Source(s): Wikipedia, Clemson