Longest Increasing Subsequence (LIS) Problem Basic

One other famous Dynamic Problem is Longest Increasing Subsequence (LIS) problem.

There are two ways (as I know of) to solve LIS problems using the Dynamic approach; however, I will discuss the easier and more intuitive solution.

 Longest Increasing Subsequence

First, we need to find out what is LIS problem.

LIS problem is "to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. "

Let's say that you are given an array containing 10 20 10 30 20 50, then LIS for the array is 4 which is {10, 20, 30, 50}.

I will use the bottom-up approach of dynamic programming to fill out all the possible LIS for each given position, and I will continually update the LIS as the position increase.

This will prevent us from recalculating overlapping subproblems and in which we can easily apply substructure properties.

Down below is a simple code for solving LIS problem:

void SolveLIS() {

for (int i = 1; i <= sFirst.size(); i++) {

for (int j = 1; j <= sSecond.size(); j++) {

if (sFirst[i-1] == sSecond[j-1]) {

iSaveList[i][j] = iSaveList[i - 1][j - 1] + 1;

}

else {

iSaveList[i][j] = max(iSaveList[i][j - 1], iSaveList[i-1][j]);

}

}

}

}

References: 

https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/

https://www.interviewbit.com/blog/longest-increasing-subsequence/

https://afteracademy.com/blog/longest-increasing-subsequence

GitHub:

https://github.com/AdvancedUno/AlgorithmProblems/tree/main/Backtrack_Shortest_Path/LCS