dynamic-programming Subsequence Related Algorithms Longest Increasing Subsequence
Example
The task is to find the length of the longest subsequence in a given array of integers such that all elements of the subsequence are sorted in ascending order. For example, the length of the longest increasing subsequence(LIS) for {15, 27, 14, 38, 26, 55, 46, 65, 85} is 6 and the longest increasing subsequence is {15, 27, 38, 55, 65, 85}. Again for {3, 4, -1, 0, 6, 2, 3} length of LIS is 4 and the subsequence is {-1, 0, 2, 3}. We'll use dynamic programming to solve this problem.
Let's take the second example: Item = {3, 4, -1, 0, 6, 2, 3}. We'll start by taking the an array dp of the same size of our sequence. dp[i] represents the length of the LIS if we include the ith item of our original sequence. At the very beginning we know that for each and every item at least the longest increasing subsequence is of length 1. That is by considering the single element itself. So we'll initialize the dp array with 1. We'll have two variables i and j. Initially i will be 1 and j will be 0. Our array will look like:
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
The number above the array represents the corresponding element of our sequence. Our strategy will be:
if Item[i] > Item[j]
dp[i] := dp[j] + 1
That means if element at i is greater than element at j, the length of the LIS that contains element at j, will increase by length 1 if we include element at i with it. In our example, for i = 1 and j = 0, Item[i] is greater than Item[j]. So dp[i] = dp[j] + 1. Our array will look like:
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
At each step, we'll increase j up to i and then reset j to 0 and increment i. For now, j has reached i, so we increment i to 2.
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
For i = 2, j = 0, Item[i] is not greater than Item[j], so we do nothing and increment j.
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
For i = 2, j = 1, Item[i] is not greater than Item[j], so we do nothing and since j has reached its limit, we increment i and reset j to 0.
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
For i = 3, j = 0, Item[i] is not greater than Item[j], so we do nothing and increment j.
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
For i = 3, j = 1, Item[i] is not greater than Item[j], so we do nothing and increment j.
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
For i = 3, j = 2, Item[i] is greater than Item[j], so dp[i] = dp[j] + 1. After that since j has reached its limit, again we reset j to 0 and increment i.
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
For i = 4 and j = 0, Item[i] is greater than Item[j], so dp[i] = dp[j] + 1. After that, we increment j.
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 2 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
For i = 4 and j = 1, Item[i] is greater than Item[j]. We can also notice that dp[i] = dp[j] + 1 will provide us 3, which means if we take the LIS for Item[j] and add Item[i] with it, we'll get a better LIS{3,4,6} than before {3,6}. So we set dp[i] = dp[j] + 1. Then we increment j.
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 3 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
For i = 4 and j = 2, Item[i] is greater than Item[j]. But for this case, if we set dp[i] = dp[j] + 1, we'll get 2, which is{-1,6} not the best{3,4,6} we can do using Item[i]. So we discard this one. We'll add a condition to our strategy, that is:
if Item[i]>Item[j] and dp[i]<dp[j] + 1
dp[i] := dp[j] + 1
We increment j by 1. Following this strategy, if we complete our dp array, it will look like:
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 3 | 3 | 4 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Now we'll iterate through this array and find out the maximum value, which will be the length of the LIS. Our pseudo-code will be:
Procedure LISLength(Item):
n := Item.length
dp[] := new Array(n)
for i from 0 to n
dp[i] := 1
end for
for i from 1 to n
for j from 0 to i
if Item[i]>Item[j] and dp[i]<dp[j] + 1
dp[i] := dp[j] + 1
end if
end for
end for
l := -1
for i from 0 to n
l := max(l, dp[i])
end for
Return l
The time complexity of this algorithm is O(n²) where n is the length of the sequence.
To find out the original sequence, we need to iterate backwards and match it with our length. The procedure is:
Procedure LIS(Item, dp, maxLength):
i := Item.length
while dp[i] is not equal to maxLength
i := i - 1
end while
s = new Stack()
s.push(Item[i])
maxLength := maxLength - 1
current := Item[i]
while maxLength is not equal to 0
i := i-1
if dp[i] := maxLength and Item[i] < current
current := Item[i]
s.push(current)
maxLength := maxLength - 1
end if
end while
while s is not empty
x := s.pop
Print(s)
end while
The time complexity of this algorithm is: O(n).
