https://algo.monster/problems/longest_increasing_subsequence
Hello! It looks like there some typo in your markdown content for the examples. I see a part of markdown table syntax there :P.
Hi, we updated the example!
Hi, Isn’t it more of two pointer than the Dynamic programming?
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.”
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]);
}
}
}```@abhi
Couldn’t agree more.
By the way, nicely done.
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.
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]