Longest Increasing Subsequence (LeetCode 300)

To find the length of the longest strictly increasing subsequence, define dp[i] as the length of the longest increasing subsequence ending at index i. Initialize all entries to 1. For each element, compare it with all previous elements; if the current element is greater, update dp[i] using the maximum value from prior valid subsequences.

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

Time complexity: O(n²), Space complexity: O(n).

Longest Continuous Increasing Subsequence (LeetCode 674)

Here, the subsequence must be contiguous. Define dp[i] as the length of the continuous increasing sequence ending at index i. If nums[i] > nums[i - 1], then dp[i] = dp[i - 1] + 1; otherwise, it remains 1.

int findLengthOfLCIS(vector<int>& nums) {
    if (nums.size() <= 1) return nums.size();
    vector<int> contLen(nums.size(), 1);
    int maxContLen = 1;
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] > nums[i - 1]) {
            contLen[i] = contLen[i - 1] + 1;
        }
        maxContLen = max(maxContLen, contLen[i]);
    }
    return maxContLen;
}

Time complexity: O(n), Space complexity: O(n).

Maximum Length of Repeated Subarray (LeetCode 718)

Use a 2D DP table where dp[i][j] represents the length of the common subarray ending at nums1[i - 1] and nums2[j - 1]. If the elements match, extend the previous diagonal value by one.

int findLength(vector<int>& nums1, vector<int>& nums2) {
    vector<vector<int>> commonLen(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
    int maxCommon = 0;
    for (int i = 1; i <= nums1.size(); ++i) {
        for (int j = 1; j <= nums2.size(); ++j) {
            if (nums1[i - 1] == nums2[j - 1]) {
                commonLen[i][j] = commonLen[i - 1][j - 1] + 1;
                maxCommon = max(maxCommon, commonLen[i][j]);
            }
        }
    }
    return maxCommon;
}

Time complexity: O(m·n), Space complexity: O(m·n).