Longest Increasing Subsequence (LIS)

The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

Examples

Example 1

Input Array: [50, 3, 10, 7, 40, 80]
LIS: [3, 7, 40, 80] (or [3, 10, 40, 80])
Output Length: 4

Example 2

Input Array: [3, 10, 2, 1, 20]
LIS: [3, 10, 20]
Output Length: 3

Example 3

Input Array: [3, 2]
LIS: [3] or [2]
Output Length: 1

Dynamic Programming Formulation

Let lis[i] be the length of the LIS ending at index i.

Base Case: lis[i] = 1 for all 0 <= i < n (since a single element is always an increasing subsequence of length 1).
Recurrence Relation: lis[i] = 1 + max(lis[j]) for all 0 <= j < i where arr[j] < arr[i].
Final Result: max(lis[i]) for all 0 <= i < n.

1. DP Tabulation Solution - O(N^2)

function lisTabulation(arr) {
    const n = arr.length;
    if (n === 0) return 0;
 
    // Initialize LIS values for all indexes as 1
    const lis = new Array(n).fill(1);
 
    // Compute optimized LIS values in bottom-up manner
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
                lis[i] = lis[j] + 1;
            }
        }
    }
 
    // Return the maximum value in lis array
    return Math.max(...lis);
}
 
// Driver code
const arr = [10, 22, 9, 33, 21, 50, 41, 60, 80];
console.log("Length of LIS is:", lisTabulation(arr));
// Output: Length of LIS is: 6 (Subsequence: 10, 22, 33, 50, 60, 80)

2. Optimized Binary Search Solution - O(N log N)

We can optimize LIS to O(N log N) time complexity by maintaining an array tails where tails[i] stores the smallest tail of all increasing subsequences of length i + 1 found so far.

function lisBinarySearch(arr) {
    if (arr.length === 0) return 0;
 
    const tails = [];
 
    for (let x of arr) {
        let left = 0;
        let right = tails.length;
 
        // Binary search to find the insert position
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (tails[mid] < x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
 
        // Replace or append the element
        if (left === tails.length) {
            tails.push(x);
        } else {
            tails[left] = x;
        }
    }
 
    return tails.length;
}

Variations of LIS

1. Building Bridges

Problem: Consider a 2D map with a horizontal river passing through its center. There are n cities on the southern bank with x-coordinates s[0]..s[n-1] and n cities on the northern bank with x-coordinates n[0]..n[n-1]. Connect as many north-south pairs of cities as possible with bridges such that no two bridges cross.

Strategy:

Group the bridges as pairs (southern_coord, northern_coord).
Sort the bridges based on one coordinate (e.g., southern_coord) in ascending order. If two southern coordinates are identical, sort by northern_coord.
Find the LIS of the other coordinate (northern_coord) of the sorted bridges. The length of this LIS is the maximum number of non-crossing bridges.

2. Maximum Sum Increasing Subsequence (MSIS)

Problem: Find the maximum sum of an increasing subsequence of a given array.

function maxSumIS(arr) {
    const n = arr.length;
    const msis = [...arr]; // Initialize MSIS values with array elements
 
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (arr[i] > arr[j] && msis[i] < msis[j] + arr[i]) {
                msis[i] = msis[j] + arr[i];
            }
        }
    }
 
    return Math.max(...msis);
}
 
// Driver code
const arrMSIS = [1, 101, 2, 3, 100, 4, 5];
console.log("Max Sum Increasing Subsequence:", maxSumIS(arrMSIS));
// Output: 106 (Subsequence: 1, 2, 3, 100)

3. Longest Bitonic Subsequence (LBS)

Problem: Find the length of the longest subsequence that is first increasing, then decreasing.

function lbs(arr) {
    const n = arr.length;
    if (n === 0) return 0;
 
    // Step 1: Compute LIS values from left to right
    const lis = new Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
                lis[i] = lis[j] + 1;
            }
        }
    }
 
    // Step 2: Compute LDS (Longest Decreasing Subsequence) values from right to left
    const lds = new Array(n).fill(1);
    for (let i = n - 2; i >= 0; i--) {
        for (let j = n - 1; j > i; j--) {
            if (arr[i] > arr[j] && lds[i] < lds[j] + 1) {
                lds[i] = lds[j] + 1;
            }
        }
    }
 
    // Step 3: Find max(lis[i] + lds[i] - 1)
    let maxLen = 0;
    for (let i = 0; i < n; i++) {
        maxLen = Math.max(maxLen, lis[i] + lds[i] - 1);
    }
 
    return maxLen;
}
 
// Driver code
const arrLBS = [1, 11, 2, 10, 4, 5, 2, 1];
console.log("Length of LBS is:", lbs(arrLBS));
// Output: 6 (Subsequence: 1, 2, 10, 5, 2, 1)

Complexity Analysis

Time Complexity:
- Standard LIS: O(N^2) (optimized to O(N log N) with Binary Search).
- MSIS and LBS: O(N^2).
Space Complexity: O(N) to store DP states.

Edit Distance Problem Collect Max Coins