Longest Increasing Subsequence - Dynamic Programming / Dynamic number of subproblems

Problems
1

https://algo.monster/problems/longest_increasing_subsequence

2

Hello! It looks like there some typo in your markdown content for the examples. I see a part of markdown table syntax there :P.

3

Hi, we updated the example!

4

Hi, Isn’t it more of two pointer than the Dynamic programming?

5

Please fix typo in this sentence → “If a number before current number is smaller than current number nums[j] < nums[i], then we can update dp[i] to be max(d[i], dp[j] + 1). dp[j] + 1 because the new subsequence is whatever the subsequence ending in j plus the current element.”

Correct sentence would be → “If a number before current number is smaller than current number nums[j] < nums[i], then we can update dp[i] to be max(dp[i], dp[j] + 1). dp[j] + 1 because the new subsequence is whatever the subsequence ending in j plus the current element.”

6

I would be great if we can provide both the top-down and the bottom-up solutions for these DP problems. Looking at 2 different solution approach helps in visualization of the problem better:

My top-down approach solution:

    public static int longestSubLen(List<Integer> nums) {
        if (nums.size() == 0) {
            return 0;
        }
        
        int[] dp = new int[nums.size()];
        
        for (int i=0; i<nums.size(); i++) {
            compute(i, nums, dp);
        }
        
        int max = 1;
        for (int i=0; i<dp.length; i++) {
            max = Math.max(max, dp[i]);
        }
        return max;
    }
    
    private static void compute(int index, List<Integer> nums, int[] dp) {
        if (dp[index] != 0) {
            return;
        }

        dp[index] = 1;
        for (int j = index+1; j<nums.size(); j++) {
            if (nums.get(index) < nums.get(j)) {
                compute(j, nums, dp);
                dp[index] = Math.max(dp[index], 1 + dp[j]); 
            }
        }
    }```
7

@abhi
Couldn’t agree more.
By the way, nicely done.

8

Shouldn’t the best variable be initialized to 1 instead 0? This is because if the largest increasing sequence is of size 1 (which it is always at least 1) we will be returning best = 0 which is incorrect.

9

https://leetcode.com/problems/longest-increasing-subsequence/solution/

10

In the “DP and binary search” figure, in the following text, “a[i]” should be “nums[i]”.
if (dp[j-1] , nums[i] && nums[i] < dp) dp[j] = a[i]

11

A simple code using bisect

from typing import List
import bisect

def longest_sub_len(nums: List[int]) → int:
# WRITE YOUR BRILLIANT CODE HERE

lis = []

for num in nums:
    
 #lower bound value, if element matched return the left most index, so that we can not add duplicate
    pos = bisect.bisect_left(lis, num)
  
 # if element is not present it return an index of len, which we can not just create with lis[pos], so we need to append it
    if pos >= len(lis):
        lis.append(num)
    else:
        lis[pos] = num
        
         # print(f"num: {num} lis: {lis}")

return len(lis)