Longest Increasing Subsequence

Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the relative order of the remaining characters.

• For example, "cat" is a subsequence of "crabt".

Examples

Example 1:

Input: nums = [9,1,4,2,3,3,7]

Output: 4

Explanation: The longest increasing subsequence is [1,2,3,7], which has a length of 4.

Example 2:

Input: nums = [0,3,1,3,2,3]

Output: 4

Constraints

• 1 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000

You should aim for a solution as good or better than O(n ^ 2) time and O(n ^ 2) space, where n is the size of the input array.

Solution

DFS returns the longest increasing subsequence we can build after having previously selected nums[prev].

class Solution {
public:
    int lengthOfLIS(const vector<int>& nums) {
        // memo[prev + 1] since prev starts at -1
        std::vector<int> memo(nums.size() + 1, -1);
 
        std::function<int(int)> dfs;
        
        // dfs(prev) returns the longest increasing subsequence we can build
        // after having previously selected nums[prev].
        //
        // If prev == -1, nothing has been selected yet, so we are free to choose
        // any index as the first element.
        dfs = [&](int prev) -> int {
            // Previously seen result
            if (memo[prev + 1] != -1) { return memo[prev + 1]; }
            int best = 0;
            for (int next = prev + 1; next < nums.size(); ++next) {
                if (prev == -1 || nums[prev] < nums[next]) {
                    best = std::max(best, 1 + dfs(next));
                }
            }
            memo[prev + 1] = best;
            return best;
        };
        return dfs(-1);
    }
};