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 to Solve

The 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: Create a dp array of the same size as nums, and initialize each element to 1 (since a single element itself is an increasing subsequence of length 1).

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 including nums[i]. Update dp[i] to be the maximum of its current value and dp[j] + 1.

3. Result: After iterating through all elements, the maximum value in the dp array will be the length of the longest increasing subsequence.

Explanation

The dynamic programming approach builds up the solution iteratively. At each step, dp[i] represents the optimal solution for the subproblem ending at index i. By considering all possible extensions of subsequences ending at previous indices, we ensure we find the globally optimal solution.

Code (Python)

def lengthOfLIS(nums):
    """
    Finds the length of the longest increasing subsequence in a given array.

    Args:
        nums: A list of integers.

    Returns:
        The length of the longest increasing subsequence.
    """
    n = len(nums)
    if n == 0:
        return 0

    dp = [1] * n  # Initialize dp array with 1s

    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

Complexity Analysis

• Time Complexity: O(n^2), due to the nested loops in the dynamic programming solution.
• Space Complexity: O(n), to store the dp array. This is linear space complexity. There are other, more space-efficient solutions that exist but are slightly more complex to implement.