Longest Increasing Subsequence

Leetcode Problem 300: Longest Increasing Subsequence

Problem Summary

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 array by deleting some or no elements without changing the order of the remaining elements. The array length is between 1 and 2500, and each value is in the range [-10^4, 10^4].

Techniques

• Array
• Dynamic Programming
• Binary Search

Solution

function lengthOfLIS(nums: number[]): number {
    const results = Array(nums.length).fill(1)

    for (let i = nums.length - 1; i >= 0; i--) {
        for (let k = nums.length - 1; k > i; k--) {
            if (nums[k] > nums[i]) {
                results[i] = Math.max(results[i], 1 + results[k])
            }
        }
    }

    return Math.max(...results)
};