Longest Increasing Subsequence (LIS)

Problem: Given an unsorted array, find the length of the longest increasing subsequence.

Dynamic Programming Approach:

1. Define DP array: Let lis[i] represent the length of the longest increasing subsequence ending at index i.
2. Transition: For each i, iterate through all j < i, and if nums[i] > nums[j], update lis[i] = max(lis[i], lis[j] + 1).
3. Initialization: Set all values in lis to 1, since each element alone is a subsequence of length 1.
4. Traversal Order: Traverse from left to right, as each value depends on earlier entries.
5. Result: The maximum value in the lis array is the length of the LIS.

Code Example:

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

Longest Continuous Increasing Subsequence (LCIS)

Problem: Find the length of the longest continuous increasing subsequence.

Dynamic Programming Approach:

1. Define DP array: Let lcis[i] represent the length of the longest continuous increasing subsequence ending at index i.
2. Transition: If nums[i] > nums[i - 1], then lcis[i] = lcis[i - 1] + 1.
3. Initialization: Each element starts with a value of 1.
4. Traversal Order: Traverse from left to right, updating based on the previous element.
5. Result: Track the maximum value in the lcis array.

Code Example:

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

Longest Common Subarray

Problem: Given two integer arrays, find the length of the longest common subarray.

Dynamic Programming Approach:

1. Define DP matrix: Let dp[i][j] be the length of longest common subarray ending at nums1[i - 1] and nums2[j - 1].
2. Transition: If nums1[i - 1] == nums2[j - 1], then dp[i][j] = dp[i - 1][j - 1] + 1.
3. Initialization: Initialize all values in dp to 0. Only update when a match is found.
4. Traversal Order: Iterate through both arrays, updating the DP matrix accordingly.
5. Result: Track the maximum value in the dp matrix.

Code Example:

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 maxLen = 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;
                    maxLen = max(maxLen, dp[i][j]);
                }
            }
        }
        return maxLen;
    }
};