Longest Increasing Subsequence medium

Problem Statement

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 Explanation: The longest increasing subsequence is [0,1,2,3], therefore the length is 4.

Steps and Explanation

This problem can be efficiently solved using dynamic programming. We'll create a dp array where dp[i] stores the length of the longest increasing subsequence ending at index i.

1. Initialization: Initialize a dp array of the same size as nums, filled with 1s. Each element initially represents a subsequence of length 1 (the element itself).

2. Iteration: Iterate through the nums array. For each element nums[i]:

   • Iterate through the elements before it (from 0 to i-1).
   • If nums[j] < nums[i], it means we can extend the increasing subsequence ending at j by adding nums[i].
   • Update dp[i] to be the maximum of its current value and dp[j] + 1.

3. Finding the Maximum: After iterating through all elements, the maximum value in the dp array represents the length of the longest increasing subsequence.

Code (TypeScript)

function lengthOfLIS(nums: number[]): number {
    if (nums.length === 0) return 0;

    const dp: number[] = new Array(nums.length).fill(1); // Initialize dp array

    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[i], dp[j] + 1); // Extend subsequence
            }
        }
    }

    return Math.max(...dp); // Find the maximum length
};

Complexity

• Time Complexity: O(n^2), due to the nested loops.
• Space Complexity: O(n), for the dp array. This can be optimized to O(m) where m is the length of the longest increasing subsequence, but the O(n) solution is simpler to understand.

This solution provides a clear and efficient way to solve the Longest Increasing Subsequence problem in TypeScript. Remember that while there are more optimized solutions (using binary search for example, achieving O(n log n) time complexity), this dynamic programming approach is easier to understand and implement for beginners.