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 an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

 

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

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

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

 

Constraints:

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    let max = 1;
    let dp = Array(nums.length).fill(1);

    for (let i = 1; i < nums.length; ++i) {
        for (let j = 0; j < i; ++j) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[j] + 1, dp[i]);
                max = Math.max(dp[i], max);
            }
        }
    }
    return max;
};

We will implement a DP solution. Let dp[i] be the longest increasing subsequence of nums[0:i + 1] that includes (ie. ends at) nums[i].

• For the base case, if i = 0, then the longest increasing subsequence of nums[0:1] is 1.
• For the recursive case, the longest increasing subsequence that include nums[i] is the longest previous subsequence that ends on a value less than the current element plus one (ie. iterate through all previous values in dp and nums).

Note that we also keep track of the global max subsequence length to return.

Follow-up

Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Solution