Problem 300: Longest Increasing Subsequence

Given an integer array, determine the length of the longest strictly increasing subsequence. A subsequence is derived by deleting zero or more elements without changing the order of remainign elements. Example: - Input: [10, 9, 2, 5, 3, 7, 101, 18] - Output: 4 - Explanation: The longest increasing subsequence is [2, 3, 7, 101]. ### Dynamic Programming Approach

1. State Definition: lisLengths[i] represents the length of the longest increasing subsequence ending at index i.
2. State Transition: For each position i, compare with all previous positions j. If arr[i] > arr[j], update lisLengths[i] = max(lisLengths[i], lisLengths[j] + 1).
3. Initialization: Each element starts with a subsequence length of 1.
4. Iteration Order: Process elements from left to right.
5. Result Extraction: Track the maximum value during iteration.

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

Problem 674: Longest Continuous Increasing Subsequence

Find the length of the longest continuous increasing subsequence in an unsorted array. A continuous increasing subsequence requires consecutive elements to be strictly increasing. Example: - Input: [1, 3, 5, 4, 7] - Output: 3 - Explanation: The longest continuous increasing subsequence is [1, 3, 5]. ### Dynamic Programming Approach

1. State Definition: contLengths[i] represents the length of the longest continuous increasing subsequence ending at index i.
2. State Transition: If arr[i] > arr[i-1], then contLengths[i] = contLengths[i-1] + 1.
3. Initialization: Each element starts with a length of 1.
4. Iteration Order: Process elements from left to right.
5. Result Extraction: Track maximum length during iteration.

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

Problem 718: Longest Repeated Subarray

Given two integer arrays, find the length of the longest comon subarray (contiguous elements). Example: - Input: A = [1, 2, 3, 2, 1], B = [3, 2, 1, 4, 7] - Output: 3 - Explanation: The longest common subarray is [3, 2, 1]. ### Dynamic Programming Approach

1. State Definition: commonLengths[i][j] represents the length of the longest common subarray ending at A[i-1] and B[j-1].
2. State Transition: If A[i-1] == B[j-1], then commonLengths[i][j] = commonLengths[i-1][j-1] + 1.
3. Initialization: All value start at 0.
4. Iteration Order: Process all elements of first array outer loop, second array inner loop.
5. Result Extraction: Track maximum value during iteration.

class Solution {
public:
    int findLength(vector<int>& arrA, vector<int>& arrB) {
        vector<vector>> commonLengths(arrA.size() + 1, vector<int>(arrB.size() + 1, 0));
        int maxCommon = 0;
        for (int i = 1; i <= arrA.size(); i++) {
            for (int j = 1; j <= arrB.size(); j++) {
                if (arrA[i-1] == arrB[j-1]) {
                    commonLengths[i][j] = commonLengths[i-1][j-1] + 1;
                    maxCommon = max(maxCommon, commonLengths[i][j]);
                }
            }
        }
        return maxCommon;
    }
};</int></vector></int></int>