Longest Increasing Subsequence
In this topic, we will learn how to find the longest increasing subsequence in an array using dynamic programming. The longest increasing subsequence is a problem that is used to find the length of the longest subsequence from the given subsequences in which all the elements are sorted in increasing order.
Let’s understand through an example.
Consider an array which is given below:
Array: 0, 4, 12, 2, 10, 6, 9, 13, 3, 11, 7, 15
The following are the subsequences that can be made from the above array:
Sub1: 8, 20, 40, 60, 70
Sub2: 9, 21, 32, 49, 60, 70
Likewise, there could be a greater number of subsequences in an array. The length of sub2 is the largest of all the subsequences. The elements in a subsequence should not be consecutive in the original array. Now let’s see how we can directly say that sub2 is the largest subsequence. We can find the longest subsequence using dynamic programming.
By using the dynamic programming approach, we are going to trace the original array at each position. We will check each index of the array that whether it is suitable for the longest increasing subsequence or not.
First, we consider two variables, i and j, where ‘i’ variable will point to each position of the array and for every ‘i’, ‘j’ will start from the beginning. We will consider two arrays named ‘length’ and ‘subsequence’, where the length array will store the length of each subsequence, and the subsequence will store the elements of subsequence.
The base condition of the dynamic programming is that we initialize each array cell with 1 value shown below. We are considering that every single element in an array is the longest increasing subsequence of length 1.
At i=0
Now we will find the subsequence whose length is greater than 1. If we start with an i=0; a[0] contains the 1 value, which is the largest increasing subsequence until now and it is already found. So, we start with an index i=1, and for every increment of ‘i’, ‘j’ will again start from the beginning.
At index i=1, j=0
Since a[i]>a[j], i.e., 4>0 means that the elements are in the increasing sequence. The length at index ‘i’ would be equal to the length at the index ‘j’ plus 1, i.e., 1+1 = 2. The value 2 will be added at the index 1 in the length array shown as below:
The previous index of ‘i’ would be added at the location ‘1’ in the subsequence array, which is shown below:
Since ‘j’ reached ‘i’, so ‘i’ will be incremented; the value of ‘i’ becomes 2 and the value of ‘j’ would again start from the beginning, i.e., 0.
At index i=2, j=0
Now we will compare a[i] and a[j]. Since a[i] is greater than a[j], i.e., 12>0 means that the elements are in increasing sequence. The length at index ‘i’ would be equal to the length at the index ‘j’ plus 1, i.e., 1+1 = 2. The value 2 would be added at the index 2 in the length array, and ‘j’ would be incremented shown as below:
At i=2, j=1
Since a[i] is greater than a[j], i.e., 12>4 means that the elements are in increasing sequence. The length at index ‘i’ would be equal to the length at the index ‘j’ plus 1, i.e., 2+1 = 3. We will compare the calculated value with the previously stored value at index i. Since 3>2, so 2 is replaced with a value 3 at the index ‘i’ in the length array shown as below:
The previous index of ‘i’ would be added at the index 2 in the subsequence array shown as below:
Since ‘j’ reached ‘i’, so ‘i’ will be incremented; the value of ‘i’ becomes 3, and the value of ‘j’ would again start from the beginning, i.e., 0.
At index i=3, j=0
Now we will compare a[i] and a[j]. Since a[i] is greater a[j], i.e., 2>0 means that the elements are in the increasing sequence. The length at the index i=3 would be equal to the length at the index ‘j’ plus 1, i.e., 1+1 = 2. The value 2 will be added at the index 3 in the length array and ‘j’ would be incremented shown as below:
Before increment of ‘j’, ‘j’ points to the index 0. The value ‘0’ would be at the index 3 in the subsequence array shown as below. Since ‘j’ does not reach ‘i’, so value 0 is not fixed at index 3 in the subsequence array.
At j=1
Now, ‘j’ points to index 1. The value at a[j] is 4 and a[i] is 2 means that a[i]<a[j]. We will increment ‘j’ as 4 is not less than 2. Once the ‘j’ gets incremented, the value of ‘j’ becomes 2.
At j=2
When ‘j’ gets incremented, we will compare a[i] and a[j]. Since a[j] is greater than a[i], i.e., 12>2 means that there would be no updation. Now, ‘j’ will be incremented, and the value of ‘j’ would become equal to ‘i’, so there would be no scope to increment the value of ‘j’.
Since ‘j’ reached ‘i’, so ‘i’ will be incremented; the value of ‘i’ becomes 4, and the value of ‘j’ would again start from the beginning, i.e., 0.
At index i=4, j=0
Now we will compare a[i] and a[j]. Since a[i] is greater than a[j], i.e., 10>0 means that the elements are in the increasing sequence. The length at the index i=4 would be equal to the length at the index ‘j’ plus 1, i.e., 1+1 = 2. The value 2 will be added at the index 4 in the length array, and ‘j’ would be incremented shown as below:
Before increment of ‘j’, ‘j’ points to the index 0. The value ‘0’ would be added at the index 4 in the subsequence array shown as below. Since ‘j’ does not reach ‘i’, so value 0 is not fixed at index 4 in the subsequence array.
At j=1
Now, ‘j’ points to index 1. The value at a[j] is 4 and a[i] is 10 means that a[i]>a[j]. The length at the index i=4 would be equal to the length at the index ‘j’ plus 1, i.e., 2+1 = 3. The value 3 will be added at the index 4 in the length array, and ‘j’ would be incremented shown below:
Before increment of ‘j’, ‘j’ points to the index 1. The value ‘1’ would be added at index 4 in the subsequence array shown as below. Since ‘j’ does not reach ‘i’, so value 1 is not fixed at index 4 in the subsequence array.
At j=2
Now, ‘j’ points to index 2. The value of a[j] is 12 and the value of a[i] is 10 means that a[i]<a[j], i.e., 12>10 means that there would be no updation. Now, ‘j’ will be incremented, and the value of ‘j’ would become 3.
At j=3
Since a[i]>a[j], i.e., 10>2 means that the elements are in the increasing sequence. The length at the index i=4 would be equal to the length at the index ‘j’ plus 1, i.e., 2+1 = 3. The value 3 will be added at the index 4 in the length array, and ‘j’ would be incremented shown as below:
Since ‘j’ reached ‘i’, so ‘i’ will be incremented; the value of ‘i’ becomes 5, and the value of ‘j’ would again start from the beginning, i.e., 0.
At index i= 5, j=0
Since a[i]>a[j], i.e., 6>0 means that the elements are in the increasing sequence. The length at the index i=5 would be equal to the length at the index ‘j’ plus 1, i.e., 1+1 = 2. The value 2 will be added at the index 5 in the length array, and ‘j’ would be incremented shown below:
Before increment of ‘j’, ‘j’ points to the index 0. The value ‘0’ would be added at the index 5 in the subsequence array shown as below. Since ‘j’ does not reach ‘i’, so value 0 is not fixed at index 5 in the subsequence array.
At j=1
Now, ‘j’ points to index 1. Since a[i] is greater than a[j], i.e., 4>6 means that the elements are in the increasing sequence. The length at the index i=5 would be equal to the length at the index ‘j’ plus 1, i.e., 2+1 = 3. The value 3 will be added at the index 5 in the length array, and ‘j’ would be incremented shown below:
Before increment of ‘j’, ‘j’ points to the index 1. The value ‘1’ would be added at the index 5 in the subsequence array shown as below. Since ‘j’ does not reach ‘i’, so value 1 is not fixed at index 5 in the subsequence array.
At j=2
Now, ‘j’ points to index 2. Since a[j] is greater than a[i], i.e., 12>6 means there would be no updation. Now, ‘j’ will be incremented, and the value of ‘j’ would become 3.
At j=3
Now, ‘j’ points to index 3. Since a[i] is greater than a[j], i.e., 6>2 means that the elements are in the increasing sequence. The length at the index i=5 would be equal to the length at the index ‘j’ plus 1, i.e., 2+1 = 3. The value 3 will be added at the index 5 in the length array and ‘j’ would be incremented shown below:
Before increment of ‘j’, ‘j’ points to the index 2. The value ‘2’ would be added at the index 5 in the subsequence array shown as below. Since ‘j’ does not reach ‘i’, so value 2 is not fixed at index 5 in the subsequence array.
At j=4
Now, ‘j’ points to index 4. Since a[j] is greater than a[i], i.e., 10>6 means there would be no updation. Now ‘j’ will be incremented and the value of ‘j’ would become 5 shown as below:
Since ‘j’ reaches ‘i’ so there would be no scope of incrementing the value. The value of ‘i’ will be incremented, and it becomes 6. The value of ‘j’ will start from the beginning, i.e., j=0.
At index i=6, j=0
Since a[i]>a[j], i.e., 9>0 means that the elements are in the increasing sequence. The length at the index i=6 would be equal to the length at the index j=0 plus 1, i.e., 1+1 =2. The value 2 will be added at the index i=6 in the length array, and ‘j’ would be incremented shown as below:
Before increment of ‘j’, ‘j’ points to the index 0. The value ‘0’ would be added at the index 6 in the subsequence array shown as below. Since ‘j’ does not reach ‘i’, so value 0 is not fixed at index 6 in the subsequence array.
At j=1
Now ‘j’ points to the index 1. Since a[i] is greater than a[j], i.e., 9>4 means that the elements are arranged in an increasing sequence. The length at the index i=6 would be equal to the length at the index j=1 plus 1, i.e., 2+1 = 3. We will compare the value which is already stored at the index 6, i.e., 2 with a newly calculated value, i.e., 3. Since 3>2 so 2 is replaced by 3 at the index 6 in the length array shown below:
The value 1 would be added at the index 6 in the subsequence array shown as below. The value of ‘j’ would be incremented and contains the value 2.
At j=2
Now, ‘j’ points to the index 2. Since a[j] is greater than a[i], i.e., 12>9 means there would be no updation. Now ‘j’ will be incremented and the value of ‘j’ would become 3 shown as below:
At j=3
Now ‘j’ points to the index 3. Since a[i] is greater than a[j], i.e., 9>2 means that the elements are arranged in an increasing sequence. The length at the index i=6 would be equal to the length at the index j=2 plus 1, i.e., 2+1 = 3. We will compare the value which is already stored at the index 6, i.e., 3 with a newly calculated value, i.e., 3. Since both the values are same so there is no need of modification.
The value 3 would be added at the index 6 in the subsequence array shown as below and the value of ‘j’ will be incremented.
At j=4
Now, ‘j’ points to the index 4. Since a[j] is greater than a[i], i.e., 6>4 means there would be no updation. Now ‘j’ will be incremented and the value of ‘j’ would become 5.
At j=5
Now j points to the index 5. Since a[i] is greater than a[j], i.e., 9>6 means that the elements are arranged in the increasing sequence. The length at the index i=6 would be equal to the length at the index j=5 plus 1, i.e., 3+1=4. We will compare the value which is already stored at the index 6, i.e., 3 with a newly calculated value, i.e., 4. Since 4>3 so we replace 3 by 4 in the length array at index i=6 shown as below:
The value 5 would be added at the index 6 in the subsequence array shown as below and the value of ‘j’ will be incremented.
At j=6
In this case, j is equal to ‘i’ so there would be no updation. The value of ‘i’ will be incremented and the value of ‘i’ becomes 7. The ‘j’ starts from the beginning, i.e., 0.
At i=7, j=0
Since a[i] is greater than a[j], i.e., 13>0 means that the elements are arranged in an increasing sequence. The length at the index 7 would be equal to the length at the index j plus 1, i.e., 1+1=2. We will compare the value which is already stored at the index 7, i.e., 1 with a newly calculated value, i.e., 2. Since 2>1 so we replace 1 by 2 in the length array at index i=7 shown as below:
The value 0 would be added at the index 7 in the subsequence array shown as below and the value of ‘j’ will be incremented.
At j=1
Since a[i] is greater than a[j], i.e., 13>4 means that the elements are arranged in an increasing sequence. The length at the index 7 would be equal to the length at the index j plus 1, i.e., 2+1=3. We will compare the value which is already stored at the index 7, i.e., 2 with a newly calculated value, i.e., 3. Since 3>2 so we replace 2 by 3 in the length array at index i=7 shown as below:
The value 1 would be added at the index 7 in the subsequence array shown as below and the value of ‘j’ will be incremented.
At j=2
Since a[i] is greater than a[j], i.e., 13>12 means that the elements are arranged in an increasing sequence. The length at the index 7 would be equal to the length at the index j plus 1, i.e., 2+1=3. We will compare the value which is already stored at the index 7, i.e., 3 with a newly calculated value, i.e., 4. Since both the values are equal so there would be no modification and the value of ‘j’ will be incremented.
The value 2 would be added at the index 7 in the subsequence array shown as below and the value of ‘j’ will be incremented.
At j=3
Since a[i] is greater than a[j], i.e., 13>2 means that the elements are arranged in an increasing sequence. The length at the index 7 would be equal to the length at the index j plus 1, i.e., 2+1=3. We will compare the value which is already stored at the index 7, i.e., with a newly calculated value, i.e., 3. Since both the values are equal so there would be no modification and the value of ‘j’ will be incremented.
The value 3 would be added at the index 7 in the subsequence array shown as below and the value of ‘j’ will be incremented.
At j=4
Since a[i] is greater than a[j], i.e., 13>10 means that the elements are arranged in an increasing sequence. The length at the index 7 would be equal to the length at the index j plus 1, i.e., 3+1=4. We will compare the value which is already stored at the index 7, i.e., 4 with a newly calculated value, i.e., 4. Since 4>3 so we replace 3 by 5 in the length array at index i=7 shown as below:
At j=5
Since a[i] is greater than a[j], i.e., 13>6 means that the elements are arranged in an increasing sequence. The length at the index 7 would be equal to the length at the index j plus 1, i.e., 3+1=4. We will compare the value which is already stored at the index 7, i.e., 4 with a newly calculated value, i.e., 4. Since both the values are equal so there would be no modification and the value of ‘j’ will be incremented.
At j=6
Since a[i] is greater than a[j], i.e., 13>9 means that the elements are arranged in an increasing sequence. The length at the index 7 would be equal to the length at the index j plus 1, i.e., 4+1=5. We will compare the value which is already stored at the index 7, i.e., 4 with a newly calculated value, i.e., 5. Since 5>4 so we replace 4 by 5 in the length array at index i=7 shown as below:
The value 6 would be added at the index 7 in the subsequence array shown as below and the value of ‘j’ will be incremented.
In this way, we find the length of the subsequences. In the above length array, 5 is the maximum length. To find the subsequence of length 5, the corresponding cell in subsequence array is index 7. We move from index 7 to index 6, move from index 6 to index 5, move from index 5 to index 3, move from index 3 to index 0. Therefore, the indexes would be 0, 3, 5, 6, 7. The elements at these indexes are subsequences. The elements corresponding to these indices are 0, 2, 6, 9, 13.