Longest Increasing Subsequence (LIS)

The Longest Increasing Subsequence problem involves findinng the maximum length of a strictly increasing subsequence from a given sequence of length n. The subsequence elements need not be contiguous in the original sequence.

Dynamic Programming Approach (O(n²))

State Representation

• DP array: Stores the length of longest increasing subsequence ending at each position
• Initialization: All values set to 1 (each element is a subsequence of length 1)
• DP[i] represents the maximum length of increasing subsequence ending at index i

State Transition

• For each element at position i, compare with all previous elements j (0 ≤ j < i)
• If current element is greater than previous element: DP[i] = max(DP[i], DP[j] + 1)
• Otherwise, maintain current DP[i] value

vector<int> sequence = {10, 22, 9, 33, 21, 50, 41, 60};
vector<int> dp(sequence.size(), 1);

int findLIS() {
    for (int i = 1; i < sequence.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (sequence[i] > sequence[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}
</int></int>

Greedy with Binary Search (O(n log n))

Maintain a candidate sequence that represents potential longest increasing subsequence. For each element:

• If element is greater than last element in candidate sequence, append it
• Otherwise, replace the first element in candidate sequence that is not smaller than current element

vector<int> input = {3, 1, 4, 1, 5, 9, 2, 6};
vector<int> candidate;

void computeLIS() {
    candidate.push_back(input[0]);
    
    for (int num : input) {
        if (num > candidate.back()) {
            candidate.push_back(num);
        } else {
            auto pos = lower_bound(candidate.begin(), candidate.end(), num);
            *pos = num;
        }
    }
    cout << "LIS Length: " << candidate.size() << endl;
}
</int></int>

Longest Continuous Incresaing Subsequence

A variation where the subsequence must consist of contiguous elements. Uses simpler DP approach:

vector<int> data = {1, 3, 5, 4, 7};
vector<int> cont_dp(data.size(), 1);

int findLCIS() {
    for (int i = 1; i < data.size(); i++) {
        if (data[i] > data[i-1]) {
            cont_dp[i] = cont_dp[i-1] + 1;
        }
    }
    return *max_element(cont_dp.begin(), cont_dp.end());
}
</int></int>