LeetCode 300: Longest Increasing Subsequence

Given an integer array nums, find the length of the longest strictly increasing subsequence.

A subsequence is a sequence derived from an array by deleting some or no elements without changing the order of remaining elements.

Dynamic Programming Approach

Define dp[i] as the length of the longest increasing subsequence ending at index i. For each position i, we need to check all previous positions j (where j < i) to findd valid transitions.

Recurrence Relation:

• If nums[i] > nums[j], then dp[i] = max(dp[i], dp[j] + 1)
• Otherwise, nums[i] cannot extend the subsequence ending at j

Implementation:

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        
        vector<int> dp(nums.size(), 1);
        int maxLength = 0;
        
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            maxLength = max(maxLength, dp[i]);
        }
        return maxLength;
    }
};

Time Complexity: O(n²) where n is the array length Space Complexity: O(n)

---

LeetCode 674: Longest Continuous Increasing Subsequence

Given an integer array nums, find the length of the longest continuous increasing subsequence.

The key difference from the previous problem: this subsequence must be continuous (contiguous in the array).

Otpimized Approach

Since continuity is required, we only need to compare adjacent elements. This eliminates the need for nested loops.

Implementation:

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        int maxLength = 1;
        int currentLength = 1;
        
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > nums[i - 1]) {
                currentLength++;
            } else {
                currentLength = 1;
            }
            maxLength = max(maxLength, currentLength);
        }
        return maxLength;
    }
};

Time Complexity: O(n) Space Complexity: O(1)

---

LeetCode 718: Maximum Length of Repeated Subarray

Given two integer arrays nums1 and nums2, return the length of the longest common subarray (contiguous subarray) found in both arrays.

Dynamic Programming Approach

This is a 2D DP problem. Define dp[i][j] as the length of the longest common subarray ending at nums1[i-1] and nums2[j-1].

Recurrence Relation:

• If nums1[i-1] == nums2[j-1], then dp[i][j] = dp[i-1][j-1] + 1
• Otherwise, dp[i][j] = 0 (subarrays must end at current positions)

Implementation:

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        
        int maxLength = 0;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    maxLength = max(maxLength, dp[i][j]);
                }
            }
        }
        return maxLength;
    }
};

Time Complexity: O(m × n) Space Complexity: O(m × n)

Space-Optimized Version

Since we only need the previous diagonal value, we can optimize space to O(n):

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<int> prev(n + 1, 0), curr(n + 1, 0);
        
        int maxLength = 0;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    curr[j] = prev[j - 1] + 1;
                    maxLength = max(maxLength, curr[j]);
                } else {
                    curr[j] = 0;
                }
            }
            swap(prev, curr);
        }
        return maxLength;
    }
};

---

Summary

Problem	Key Characteristic	Time	Space
300. LIS	Non-contiguous subsequence	O(n²)	O(n)
674. LCIS	Contiguous subsequence	O(n)	O(1)
718. Repeated Subarray	Contiguous in both arrays	O(m×n)	O(min(m,n))