[[Dynamic Programming Primer]]

Problem

You are given an array of integers, nums. A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. Your goal is to find the length of the longest strictly increasing subsequence.

Example: nums = [10, 9, 2, 5, 3, 7, 101, 18]

• [2, 3, 7, 101] is one LIS.
• [2, 5, 7, 101] is another. The answer is 4.

Brainstorming

The core idea here is simple what should we track in our dp state?

till now we are caulcating partial solutions and storing it in our dp arrays as prefix solutions (dp[2] contains number of ways we can climb stairs 2 , least number of coins we need to make amount 2) these are exact solutions at dp[i] that can be use directly but they are not the solution. we are still building them up to our step or amount

but here the problem is a bit more complex. lets take the following example nums = [3, 4, 1, 2]

• dp[0] (for [3]): The LIS is [3]. Length is 1
• dp[1] (for [3, 4]): The LIS is [3, 4]. Length is 2
• dp[2] (for [3, 4, 1]): The LIS is still [3, 4]. Length is 2

Now, we need to calculate dp[3] for [3, 4, 1, 2]. The new number is 2. Can we use the information from dp[2] (which is just the number 2) to figure out the LIS for the whole array? Does dp[2] tell us enough?

As we know its not so we need to track another piece of information , what does the LIS at dp[i] end with? why because then we know if we can increase it further or not. since the sequence is not sorted and it can increase from any place The easiest thing we can track here is if we make sure that an LIS at dp[i] is also ending with nums[i] in that way deciding for a new number say nums[i+1] will be easier to attach

To calculate dp[i], we must look at all previous positions j (from 0 to i-1). For each j, we check if we can “attach” nums[i] to the LIS that ends at j.

so there are in a way 2 things

1. dp[i] should mean that the last element for this prefix LIS at i is nums[i]
2. in this prefix dp[i] to calculate it we need to look at all the values ranging from o to i-1 to see if we can attachnums[i] , the best one is the longest one

Now lets talk about the base case in any array the minimum length of an LIS is 1 , think about it in an array [2,2] the LIS is 1 in [1] the LIS is also 1 and we are guaranteed that the input array will not be empty.

below is the algorithm

1. Initialise the dp array of length nums dp = [1]*n # where n is the length of the nums array
2. We will have 2 for loops one that goes from 0 all the way to n-1 for each i where i is the length of the prefix for which we are calculating LIS hence dp[i] (what is the LIS in prefix of length i)
   1. inside this loop we will have another loop that goes from 0 to i-1 . for each j we try to attach nums[i] to it it will only be possible if nums[i] > nums[j] and then we add 1 to it current_lis = 1 + dp[j]
   2. then we check which is maximum the current_lis thats computed or the previous value of LIS already stored in dp[i] which by default starts at 1 dp[i] = max(dp[i], current_lis)
3. the final answer after all the tabulation may not neccessarily be at the end of the array , we can have LIS somewhere in the middle too as given in the problem statement and we don’t really care if we have duplicate LIS so we just return the max value stored in the dp state array max(dp)

below is the python implementation

nums = [3, 4, 1, 2]
n = len(nums)
dp = [1] * n

for i in range(n):
	for j in range(i)
		if nums[i] > nums[j]:
			current_lis = 1 + dp[j]
			dp[i] = max(current_lis, dp[i])

print(max(dp))