Neetcode - Longest Increasing Subsequence

Today’s hack is tomorrow’s habit.

This problem was quite tricky for me to solve. I was aware that a recursive approach could be used, but I still haven’t fully grasped the idea of how to form a subsequence from the given list. As a result, the problem felt somewhat abstract to me. Below is the basic solution provided for this task.

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        return dfs(0, -1, nums);
    }

    int dfs(int i, int j, vector<int>& nums) {
        if (i == nums.size()) return 0;

        int lis = dfs(i + 1, j, nums);
        
        if (j == -1 || nums[j] < nums[i]) {
            lis = max(lis, 1 + dfs(i + 1, i, nums));
        }

        return lis;
    }
};

The termination condition is straightforward. As we iterate from left to right, at each recursive call we decide whether to take or skip the current element. During each call, we compare values to ensure the sequence remains increasing—specifically, we take the current element only if it is greater than the previously chosen one. If no element has been chosen yet (i.e., j == -1), we are free to take the current element.

Now, let’s implement this using the top-down dynamic programming approach (with memoization).

class Solution {
private:
    vector<int> memo;

    int dfs(int i, vector<int>& nums) {
        if (memo[i] != -1) return memo[i];

        int lis = 1;
        for (int j = i + 1; j < nums.size(); ++j) {
            if (nums[i] < nums[j]) {
                lis = max(lis, 1 + dfs(j, nums));
            }
        }
        return memo[i] = lis;
    }
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        memo.assign(n, -1);

        int lis = 1;
        for (int i = 0; i < n; ++i) {
            lis = max(lis, dfs(i, nums));
        }
        return lis;
    }
};

A bottom-up approach is also provided, which I personally find the bottom-up approach more intuitive, as it clearly shows how the "pointers" move through the list and how their respective values are compared. The key point to understand is how the algorithm stores the length of the longest increasing subsequence (LIS) ending at each indexi.

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> lis(n, 1);

        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < nums.size(); ++j) {
                if (nums[i] < nums[j]) {
                    lis[i] = max(lis[i], 1 + lis[j]);
                }
            }
        }
        return *max_element(lis.begin(), lis.end());
    }
};

Also, note that we compare with 1 + lis[j] because this approach sweeps from right to left. At each index i, we look at future indices j (e.g., if i = 3, then j could be 4, 5, etc.). Here, lis[j] represents the length of the LIS already computed starting from index j, so adding 1 accounts for including the current element nums[i] in that subsequence.

Conclusion

Nice work on the DP questions! I’ve been practicing DP problems recently too, but I still don’t feel fully confident with them. So I’ll just keep grinding away until it becomes second nature.