Longest Increasing Subsequence (LIS) Algorithm

Longest Increasing Subsequence (LIS)

Algorithm Explanation

The Longest Increasing Subsequence (LIS) problem involves finding the longest subsequence of a sequence such that all elements of the subsequence are sorted in increasing order.

Dynamic Programming (O(n2)) Approach

- Initialize a dp[] array of size n where dp[i] represents the length of the LIS ending at index i.
- For each i from 1 to n-1, iterate over all j from 0 to i-1:
  If arr[i] > arr[j], update dp[i] = max(dp[i], dp[j] + 1).
- The answer is the maximum value in dp[].

Efficient Binary Search Approach (O(n log n))

- Maintain a tail[] array that stores the smallest possible tail value for all increasing subsequences with length i+1 in tail[i].
- For each element x in the input, use binary search to find the smallest index in tail where tail[i] >= x, and replace or append accordingly.

Complexity Analysis

  • Time Complexity: O(n log n) using binary search approach
  • Space Complexity: O(n) for the tail array

Easy Problems Solvable Using LIS

1. Find Length of LIS

Problem: Given an array, find the length of the LIS.


#include <iostream>
#include <vector>
#include <algorithm>

int lengthOfLIS(std::vector<int>& nums) {
    std::vector<int> tail;
    for (int num : nums) {
        auto it = std::lower_bound(tail.begin(), tail.end(), num);
        if (it == tail.end()) tail.push_back(num);
        else *it = num;
    }
    return tail.size();
}

int main() {
    std::vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    std::cout << lengthOfLIS(nums);
    return 0;
}

2. Check If Subsequence Is Increasing

Problem: Given a sequence, determine if it's an increasing subsequence of another array.


#include <iostream>
#include <vector>

bool isIncreasingSubsequence(const std::vector<int>& arr, const std::vector<int>& seq) {
    int i = 0;
    for (int num : arr) {
        if (i < seq.size() && seq[i] == num) i++;
    }
    return i == seq.size();
}

int main() {
    std::vector<int> arr = {1, 3, 5, 6, 7};
    std::vector<int> seq = {1, 5, 7};
    std::cout << isIncreasingSubsequence(arr, seq);
    return 0;
}

Intermediate Problems Solvable Using LIS

1. Maximum Sum Increasing Subsequence


#include <iostream>
#include <vector>
#include <algorithm>

int maxSumIS(std::vector<int>& arr) {
    int n = arr.size();
    std::vector<int> dp = arr;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                dp[i] = std::max(dp[i], dp[j] + arr[i]);
            }
        }
    }

    return *std::max_element(dp.begin(), dp.end());
}

int main() {
    std::vector<int> arr = {1, 101, 2, 3, 100, 4, 5};
    std::cout << maxSumIS(arr);
    return 0;
}

2. Number of LIS

Problem: Count how many distinct LIS are there.


#include <iostream>
#include <vector>
#include <algorithm>

int findNumberOfLIS(std::vector<int>& nums) {
    int n = nums.size(), maxLen = 0, res = 0;
    std::vector<int> len(n, 1), cnt(n, 1);
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                if (len[j] + 1 > len[i]) {
                    len[i] = len[j] + 1;
                    cnt[i] = cnt[j];
                } else if (len[j] + 1 == len[i]) {
                    cnt[i] += cnt[j];
                }
            }
        }
        if (len[i] > maxLen) {
            maxLen = len[i];
            res = cnt[i];
        } else if (len[i] == maxLen) {
            res += cnt[i];
        }
    }
    return res;
}

int main() {
    std::vector<int> nums = {1, 3, 5, 4, 7};
    std::cout << findNumberOfLIS(nums);
    return 0;
}

Hard Problem Solvable Using LIS

Russian Doll Envelopes

Problem: Given envelopes with widths and heights, find the max number that can be nested.


#include <iostream>
#include <vector>
#include <algorithm>

int maxEnvelopes(std::vector<std::vector<int>>& envelopes) {
    std::sort(envelopes.begin(), envelopes.end(), [](auto& a, auto& b) {
        return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
    });

    std::vector<int> dp;
    for (auto& env : envelopes) {
        auto it = std::lower_bound(dp.begin(), dp.end(), env[1]);
        if (it == dp.end()) dp.push_back(env[1]);
        else *it = env[1];
    }

    return dp.size();
}

int main() {
    std::vector<std::vector<int>> envelopes = {{5,4}, {6,4}, {6,7}, {2,3}};
    std::cout << maxEnvelopes(envelopes);
    return 0;
}