How do you find the longest increasing subsequence?

Finding the longest increasing subsequence (LIS) in a sequence of numbers is a classic problem in computer science and dynamic programming. The goal is to identify the longest subsequence where each element is greater than the preceding one. This problem can be approached in several ways, with varying time complexities. Below, I will outline the most common methods, provide practical examples, and highlight best practices and common mistakes.

Dynamic Programming Approach

The dynamic programming approach is one of the most efficient ways to solve the LIS problem. The idea is to build a table that stores the length of the longest increasing subsequence that ends with each element of the array.

Algorithm Steps

1. Initialize an array `dp` of the same length as the input array, where each element is set to 1. This is because the minimum length of LIS for any element is 1 (the element itself).
2. Iterate through the array with two nested loops. The outer loop will go through each element, while the inner loop will check all previous elements.
3. For each pair of elements, if the current element is greater than the previous one, update the `dp` array by taking the maximum of its current value and the value of the previous element plus one.
4. The length of the longest increasing subsequence will be the maximum value in the `dp` array.

Example Code

function longestIncreasingSubsequence(arr) {
    if (arr.length === 0) return 0;
    
    const dp = new Array(arr.length).fill(1);
    
    for (let i = 1; i < arr.length; i++) {
        for (let j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    
    return Math.max(...dp);
}

const exampleArray = [10, 22, 9, 33, 21, 50, 41, 60, 80];
console.log(longestIncreasingSubsequence(exampleArray)); // Output: 6

Binary Search Approach

For a more efficient solution, especially for larger datasets, a combination of dynamic programming and binary search can be used. This approach reduces the time complexity to O(n log n).

Algorithm Steps

1. Create an empty array `sub` that will store the smallest tail for all increasing subsequences found so far.
2. Iterate through each number in the input array:
3. Use binary search to find the index of the smallest number in `sub` that is greater than or equal to the current number.
4. If such a number is found, replace it with the current number; otherwise, append the current number to `sub`.
5. The length of `sub` will give the length of the longest increasing subsequence.

Example Code

function longestIncreasingSubsequence(arr) {
    const sub = [];
    
    for (let num of arr) {
        let left = 0, right = sub.length;
        
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (sub[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        if (left === sub.length) {
            sub.push(num);
        } else {
            sub[left] = num;
        }
    }
    
    return sub.length;
}

const exampleArray = [10, 22, 9, 33, 21, 50, 41, 60, 80];
console.log(longestIncreasingSubsequence(exampleArray)); // Output: 6

Best Practices

• Always consider edge cases, such as empty arrays or arrays with all identical elements.
• Optimize for performance when working with large datasets by using the binary search approach.
• Write clear and maintainable code with comments explaining the logic.

Common Mistakes

• Forgetting to initialize the `dp` array correctly can lead to incorrect results.
• Not considering the case where the input array is empty can cause runtime errors.
• Using a brute-force approach without recognizing the potential for optimization can lead to inefficient solutions.