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 and Explanation

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

1. Initialization: Initialize dp[i] = 1 for all i. This is because the minimum length of an increasing subsequence ending at any index is 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).

3. Comparison: If nums[j] < nums[i] (meaning we found a smaller element that can be part of an increasing subsequence ending at i), then we can potentially extend the subsequence. We update dp[i] as follows: dp[i] = max(dp[i], dp[j] + 1). This means the length of the LIS ending at i is the maximum of its current length and the length of the LIS ending at j plus 1 (because we're adding nums[i] to that subsequence).

4. Finding the Maximum: After iterating through the entire array, the maximum value in the dp array will be the length of the longest increasing subsequence.

Code (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int lengthOfLIS(vector<int>& nums) {
    if (nums.empty()) {
        return 0;
    }

    int n = nums.size();
    vector<int> dp(n, 1); // Initialize dp array with 1s

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    int maxLength = *max_element(dp.begin(), dp.end());
    return maxLength;
}

int main() {
    vector<int> nums1 = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "Length of LIS for nums1: " << lengthOfLIS(nums1) << endl; // Output: 4

    vector<int> nums2 = {0, 1, 0, 3, 2, 3};
    cout << "Length of LIS for nums2: " << lengthOfLIS(nums2) << endl; // Output: 4

    vector<int> nums3 = {};
    cout << "Length of LIS for nums3: " << lengthOfLIS(nums3) << endl; // Output: 0

    return 0;
}

Time and Space 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. We could potentially reduce this to O(1) using a more advanced approach (like binary search) but that would involve slightly increased complexity in other areas. This solution prioritizes readability and clarity.