Longest Increasing Subsequence (LIS)

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

There are several algorithms to solve this problem, with dynamic programming being one of the most efficient approaches.

pseudocode:

function LIS(arr):
    n = length of arr
    // Initialize an array to store the length of LIS ending at each index
    lis_length = array of size n, initialized to 1

    // Iterate through the array
    for i from 1 to n-1 do:
        // Check all previous elements
        for j from 0 to i-1 do:
            // If the current element is greater than the previous element
            if arr[i] > arr[j]:
                // Update the LIS length if adding the current element can extend the LIS
                lis_length[i] = maximum(lis_length[i], lis_length[j] + 1)

    // Find the maximum LIS length
    max_length = maximum value in lis_length

    // Reconstruct the LIS
    lis = empty array
    max_index = index of maximum value in lis_length
    lis.append(arr[max_index])

    // Traverse backwards to find the LIS elements
    for i from max_index-1 to 0 do:
        if lis_length[i] == lis_length[max_index] - 1 and arr[i] < arr[max_index]:
            // Include the element in LIS
            lis.append(arr[i])
            max_index = i

    // Return the LIS and its length
    return lis, max_length

function lis(nums) {
    const n = nums.length;
    const dp = new Array(n).fill(1); // Initialize an array to store LIS length ending at each index

    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1); // Update LIS length at index i
            }
        }
    }

    let maxLength = 0;
    for (let i = 0; i < n; i++) {
        maxLength = Math.max(maxLength, dp[i]); // Find maximum LIS length
    }

    return maxLength;
}

// Example usage:
const nums = [10, 22, 9, 33, 21, 50, 41, 60, 80];
console.log("Length of Longest Increasing Subsequence:", lis(nums)); // Output: 6

In this implementation:

• We initialize an array dp to store the length of the longest increasing subsequence ending at each index.

• We iterate through the input array nums, and for each element at index i, we iterate through the elements before it (indexes j < i), checking if nums[i] is greater than nums[j]. If it is, we update the length of the longest increasing subsequence ending at index i (dp[i]) to be the maximum of its current value and dp[j] + 1.

• After filling the dp array, we find the maximum value in it, which represents the length of the longest increasing subsequence in the entire array.

• Finally, we return the maximum length found.

This algorithm has a time complexity of O(n^2), where n is the length of the input array nums.

There are more efficient algorithms like the Patience Sorting algorithm or using binary search to reduce the time complexity to O(n log n), but the dynamic programming approach is easier to understand and implement.