300. Longest Increasnig Subsequence

Today we officially begin the subsequence series. This problem is relatively straightforward and serves as a good introduction to the thought process behind subsequence dynamic programming problesm.

class Solution {
public:
    int lengthOfLIS(vector<int>& sequence) {
        int n = sequence.size();
        if (n <= 1) return n;
        
        vector<int> lengths(n, 1);
        int longest = 1;
        
        for (int end = 1; end < n; ++end) {
            for (int start = 0; start < end; ++start) {
                if (sequence[start] < sequence[end]) {
                    lengths[end] = max(lengths[end], lengths[start] + 1);
                }
            }
            longest = max(longest, lengths[end]);
        }
        
        return longest;
    }
};

674. Longest Continuous Increasing Subsequence

Compared to the previous Longest Increasing Subsequence problem, the key difference here is continouus. Try solving it yourself first to experience the distinction.

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

718. Longest Repeating Subarray

This problem is slightly more challenging and requires utilizing a 2D DP array.

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int m = A.size(), n = B.size();
        vector<vector<int>> memo(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 (A[i - 1] == B[j - 1]) {
                    memo[i][j] = memo[i - 1][j - 1] + 1;
                    maxLength = max(maxLength, memo[i][j]);
                }
            }
        }
        
        return maxLength;
    }
};