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

Steps

The problem can be solved efficiently 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. 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 efficiently avoids redundant calculations. Instead of exploring all possible subsequences (which would be exponential), it builds up the solution incrementally. For each element, it considers only the previously calculated lengths of increasing subsequences that can be extended. This significantly reduces the time complexity.

Code (Java)

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1); // Initialize each element to have a subsequence length of 1

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

        return maxLength;
    }
}

Complexity

• Time Complexity: O(n^2), due to the nested loops in the dynamic programming approach.
• Space Complexity: O(n), to store the dp array. This is linear space complexity.