Subsequence Problems

Find the longest strictly increasing subsequence. Elements don't need to be contiguous but must maintain their original order.

$O(n^2)$ approach: dp[i] = length of LIS ending at index i dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]

`nums`	result	subsequence
`[10, 9, 2, 5, 3, 7, 101, 18]`	`4`	`[2, 3, 7, 101]`
`[5, 4, 3, 2, 1]`	`1`	all decreasing
`[7, 7, 7, 7]`	`1`	strictly increasing — equal doesn't count

Initialize all dp[i] = 1 (each element alone is a subsequence of length 1). Answer is max(dp[i]) over all i.

C++

// Find the length of the longest strictly increasing subsequence.
// A subsequence is derived by deleting some or no elements without
// changing the order of remaining elements.
int lengthOfLIS(const std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> dp(n, 1);
    int maxLen = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
        maxLen = std::max(maxLen, dp[i]);
    }
    return maxLen;
}

Longest Increasing Subsequence (LIS)

Longest Common Subsequence (LCS)