You already know that any problem of dynamic programming is solved in 3 steps: Storage & Meaning, Direction and Traversal & Solve.

We make a 1D dp array of size n as shown in figure

The marked cell in figure 2 stores the length of the Longest Increasing Subsequence (LIS) ending at 21 in the sub array [10, 22, 9, 33, 21].

We notice that the smallest problem lies for the sub array [10] and the largest problem lies for the array [10,22,9,33,21,50,41,60,80,1].

Hence, we move from left to right.

• We start our traversal from element 10. We know that 10 can have 2 subsequences: either a blank subsequence or 10 itself.



Hence, the increasing subsequence with the longest length ending at 10 is the 10 itself. So we store its length 1 in the cell.

• Let's now move on to the next sub array [10, 22]. We know that all its subsequences are [- -, - 22, 10 -, 10 22]. Out of these subsequences the required increasing LIS of maximum length ending at 22 is [10 22] of length 2.
• Similarly, for the subarray [10,22,9] the desired subsequence is 9 itself because 10 and 22 are greater than 9 and we want to form a subsequence where 9 is at the end i.e. 9 is the largest element.
• Now for the subarray [10, 22, 9, 33] we need to find the required subsequence ending at 33.

We see that since 10 is smaller than 33, therefore, we can add 33 to the subsequence of 10 to form [10,33]. Similarly, 22 and 9 are also smaller than 33 therefore 33 can be added to their subsequences to form [10,22,33] and [9,33] respectively.

Out of these three candidates, [10,22,33] has the longest length hence its length 3 will be stored in the corresponding cell.

• For the subarray [10,22,33,21], to find the desired subsequence ending at 21 we first find the elements smaller than 21 which are 10 and 9.

Hence, 21 can be added to the subsequences of 10 and 9 to form [10,21] and [9,21] respectively. So the largest length is 2.

• We want you to fill the remaining array yourself . The resultant array should lool like figure.
• We are now aware of the subsequence following all the required rules for every element. Out of all these subsequences, the longest subsequence is of length 6 ending at the element 80. Hence 6 is printed.

Java Code