[Dynamic Programming] Longest Increasing Subsequence - Medium

The Longest Increasing Subsequence (LIS) problem is a well-known challenge in dynamic programming. It looks for the longest subsequence in a list of numbers where each number is bigger than the one before it. To find the best solution, we build a dynamic programming array. This array keeps track of the longest increasing subsequence at every position. This way, we can find the answer in O(n^2) time or even O(n log n) with better methods.

In this article, we will look closely at the Longest Increasing Subsequence problem. We will explore different ways to solve it, like dynamic programming and binary search methods. We will show code examples in Java, Python, and C++. We will also talk about how to make space usage better. Plus, we will point out common mistakes to avoid and answer questions we often hear about LIS.

[Dynamic Programming] Longest Increasing Subsequence Problem Explained
Understanding the Dynamic Programming Approach
Implementing Longest Increasing Subsequence in Java
Implementing Longest Increasing Subsequence in Python
Implementing Longest Increasing Subsequence in C++
Optimizing Space Complexity for Longest Increasing Subsequence
Binary Search Approach to Longest Increasing Subsequence
Comparison of Different Approaches for Longest Increasing Subsequence
Common Mistakes to Avoid in Longest Increasing Subsequence
Frequently Asked Questions

If we want to learn more about dynamic programming techniques, we can check out related articles like the Dynamic Programming Fibonacci Number or Dynamic Programming Climbing Stairs.

Understanding the Dynamic Programming Approach

Dynamic programming is a strong method we can use to solve optimization problems. It helps us break problems into simpler parts. This approach works well for problems that have overlapping subproblems and optimal substructure.

Key Concepts

Overlapping Subproblems: We can divide the problem into smaller subproblems that we can use again. For example, in the Longest Increasing Subsequence (LIS) problem, we can reuse solutions for smaller subsequences.
Optimal Substructure: The best solution for the problem comes from the best solutions of its smaller parts. In LIS, we can create the longest subsequence by looking at the longest subsequences of elements before it.

Steps in Dynamic Programming

Define the State: We need to know what defines the solution. For LIS, we can use an array dp where dp[i] shows the length of the longest increasing subsequence that ends with the element at index i.
State Transition: We need a formula to calculate the state. For LIS:

[ dp[i] = (dp[j] + 1) j < i arr[j] < arr[i] ]
Base Case: We start with base cases. For LIS, every element is a subsequence of length 1:
```
for (int i = 0; i < n; i++) {
    dp[i] = 1;
}
```
Compute the Result: We go through the states to fill the dp array and find the answer. The result is the biggest value in the dp array.

Example

Let’s look at the array arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]. We compute the dp array like this:

Start with dp as [1, 1, 1, 1, 1, 1, 1, 1, 1].
Then we update dp by using the state transition rule.

The final dp array can be [1, 2, 1, 3, 2, 4, 3, 5, 6]. This means the longest increasing subsequence has a length of 6.

Dynamic programming helps us lower the time complexity from exponential to polynomial. This makes it easier for bigger inputs. For more about dynamic programming, we can check out topics like Dynamic Programming: Fibonacci Number and Dynamic Programming: Coin Change.

Implementing Longest Increasing Subsequence in Java

We can solve the Longest Increasing Subsequence (LIS) problem in Java using a simple method called dynamic programming. We keep an array dp. The element dp[i] shows the length of the longest increasing subsequence that ends with the item at index i.

Java Implementation:

import java.util.Arrays;

public class LongestIncreasingSubsequence {
    public static int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;

        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1); // Each item is an increasing subsequence of length 1

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        // The longest increasing subsequence length is the max value in dp
        int maxLength = 0;
        for (int length : dp) {
            maxLength = Math.max(maxLength, length);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("Length of Longest Increasing Subsequence: " + lengthOfLIS(nums));
    }
}

Explanation:

Initialization: We start by setting each item in dp to 1.
Nested Loop:
- The first loop goes through each item.
- The second loop looks at all the previous items to check if they can be part of an increasing subsequence.
Update: If nums[i] > nums[j], we change dp[i] to be the highest of its current value or dp[j] + 1.
Result: In the end, the biggest value in dp shows the length of the longest increasing subsequence.

This method takes O(n^2) time. It works well for input arrays that are not too big. If we have larger datasets, we can think about using binary search to make it faster.

Implementing Longest Increasing Subsequence in Python

We want to solve the Longest Increasing Subsequence (LIS) problem in Python. We can use a dynamic programming method. The main idea is to keep an array dp. Here, dp[i] will store the length of the longest increasing subsequence that ends with the number at index i.

Here is how we can do it:

def longest_increasing_subsequence(nums):
    if not nums:
        return 0

    n = len(nums)
    dp = [1] * n  # Each number is an increasing subsequence of length 1 by itself

    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:  # Check if the current number can extend the subsequence
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)  # The length of the longest increasing subsequence

# Example usage:
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(longest_increasing_subsequence(nums))  # Output: 4

Explanation of the Code:

Initialization: We create a dp array. We set it to 1 because each number is an increasing subsequence of at least length 1.
Nested Loops: The outer loop goes through each number. The inner loop checks all previous numbers to update the dp value.
Condition Check: If nums[i] is bigger than nums[j], it means we can add the number at i to the increasing subsequence ending at j.
Final Result: The biggest value in the dp array tells us the length of the longest increasing subsequence.

For a faster way, we can make it work in (O(n n)) using binary search. But the method we showed here is good for understanding dynamic programming. If you want to learn more about dynamic programming, you can check out this topic: Dynamic Programming: Fibonacci Number.

Implementing Longest Increasing Subsequence in C++

To solve the Longest Increasing Subsequence (LIS) problem in C++, we can use dynamic programming. We keep an array called dp. In this array, dp[i] tells us the length of the longest increasing subsequence that ends at the index i. The answer we want is the biggest number in the dp array.

Here is a simple way to implement the Longest Increasing Subsequence in C++:

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

using namespace std;

int longestIncreasingSubsequence(const vector<int>& nums) {
    if (nums.empty()) return 0;

    vector<int> dp(nums.size(), 1); // We start the dp array with 1

    for (int i = 1; i < nums.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    return *max_element(dp.begin(), dp.end()); // We return the biggest length
}

int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "Length of Longest Increasing Subsequence: " << longestIncreasingSubsequence(nums) << endl;
    return 0;
}

Explanation:

Initialization: We make a dp array that is the same size as the input array nums. We set all values to 1. This is because the smallest increasing subsequence for each element is at least 1, which is the element itself.
Nested Loops: The first loop goes through each element. The second loop checks all the previous elements to see if they can make the increasing subsequence longer.
Condition Check: If nums[i] is bigger than nums[j], we update dp[i]. We set it to the bigger of its current value or dp[j] + 1.
Result: The length of the longest increasing subsequence is the biggest number in the dp array.

This method has a time complexity of O(n^2). This is good for medium-sized inputs. For bigger inputs, we can think about using a better way that uses binary search. This can lower the time complexity to O(n log n).

If you want to learn more about dynamic programming, you might like this article on the Coin Change problem.

Optimizing Space Complexity for Longest Increasing Subsequence

When we use the Longest Increasing Subsequence (LIS) algorithm, the usual dynamic programming method needs O(n^2) time and O(n) space. But we can make the space use better and get it down to O(n) with a smarter way.

Space Optimization Techniques

Using a Single Array: We do not need a 2D array to save the lengths of increasing subsequences. We can just use one array to track the longest subsequence lengths for each index.
Binary Search with a Tail Array: We can cut down space even more by using a tail array. This array will keep the last numbers of possible subsequences. It helps us keep the smallest tail value for each length of increasing subsequence.

Implementation

We can use the optimized way with a tail array like this:

import java.util.Arrays;

public class LIS {
    public static int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        
        int[] tail = new int[nums.length];
        int length = 0;

        for (int num : nums) {
            int i = 0, j = length;
            while (i < j) {
                int mid = i + (j - i) / 2;
                if (tail[mid] < num) {
                    i = mid + 1;
                } else {
                    j = mid;
                }
            }
            tail[i] = num;
            if (i == length) length++;
        }
        return length;
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("Length of Longest Increasing Subsequence: " + lengthOfLIS(nums));
    }
}

Explanation of the Code

We have a tail array. Here, tail[i] holds the smallest tail value for all increasing subsequences of length i + 1.
For every number in the input array, we do a binary search on the tail array to find its place.
If the number makes the largest subsequence longer, we add it to the tail array. If it can replace a value, it will keep the smallest tail for that length.

Complexity Analysis

Time Complexity: O(n log n) because of binary search.
Space Complexity: O(n) for the tail array.

By making space use better this way, we can handle bigger inputs easily while keeping the performance of the Longest Increasing Subsequence algorithm.

For more about dynamic programming, we can look at other problems like the Dynamic Programming - Coin Change or Dynamic Programming - Fibonacci with Memoization.

Binary Search Approach to Longest Increasing Subsequence

We can use the Binary Search method to solve the Longest Increasing Subsequence (LIS) problem. This way, we make it faster. The time needed is O(n log n). This method uses a dynamic array to remember the smallest tail for all increasing subsequences we find so far.

Approach

Maintain a List: We use a list called tails. Here, tails[i] keeps the smallest tail of all increasing subsequences with length i + 1.
Binary Search: For each number in the input array, we use binary search. This finds the spot in tails where the current number can either replace a value or add to the list.
Update Tails: If the number is bigger than all values in tails, we add it to the end. If it is smaller, we replace the first number in tails that is bigger or equal to this number.

Implementation

Here is a simple code example of the Binary Search method for LIS in Python:

def length_of_lis(nums):
    from bisect import bisect_left

    if not nums:
        return 0

    tails = []

    for num in nums:
        pos = bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num

    return len(tails)

# Example usage
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(length_of_lis(nums))  # Output: 4

Explanation of the Code

The function length_of_lis takes a list of numbers nums.
It uses the bisect_left function from the bisect module to do binary search on the tails list.
The size of the tails list at the end shows the length of the Longest Increasing Subsequence.

Complexity Analysis

Time Complexity: O(n log n), where n is the size of the input array.
Space Complexity: O(n) for the tails list.

This binary search method is very useful for big datasets. It is a good choice for solving the Longest Increasing Subsequence problem quickly. For more information on dynamic programming methods, we can look at other articles like Dynamic Programming: Coin Change.

Comparison of Different Approaches for Longest Increasing Subsequence

We can solve the Longest Increasing Subsequence (LIS) problem in different ways. Each way has its own time and space costs. Here, we will look at three common methods: the Naive Approach, Dynamic Programming, and Binary Search with Dynamic Programming.

1. Naive Approach

Time Complexity: O(2^n)
Space Complexity: O(n)
Description: This way makes all subsequences and checks which ones are increasing. It is not good for big input sizes.

def longest_increasing_subsequence(arr):
    def lis_ending_at(i):
        max_length = 1
        for j in range(i):
            if arr[j] < arr[i]:
                max_length = max(max_length, lis_ending_at(j) + 1)
        return max_length

    max_lis = 0
    for i in range(len(arr)):
        max_lis = max(max_lis, lis_ending_at(i))
    return max_lis

2. Dynamic Programming Approach

Time Complexity: O(n^2)
Space Complexity: O(n)
Description: This way uses a DP array. Here, dp[i] shows the length of the longest increasing subsequence that ends with arr[i].

public int longestIncreasingSubsequence(int[] nums) {
    if (nums.length == 0) return 0;
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    return Arrays.stream(dp).max().getAsInt();
}

3. Binary Search with Dynamic Programming

Time Complexity: O(n log n)
Space Complexity: O(n)
Description: This better way keeps a temporary array. This array holds the smallest tail of all increasing subsequences we found. We use binary search to find where each element goes.

#include <vector>
#include <algorithm>

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

Summary of Approaches

The Naive approach does not work well for larger datasets because it takes too much time.
The Dynamic Programming approach is much better but still takes a lot of time.
The Binary Search approach is the best. It cuts down the time to O(n log n), so it works good for larger input sizes.

For more on dynamic programming, we can look at Dynamic Programming Fibonacci Number or Dynamic Programming Coin Change.

Common Mistakes to Avoid in Longest Increasing Subsequence

When we work on the Longest Increasing Subsequence (LIS) algorithm, we can face some common mistakes. These can give us wrong results or slow solutions. Here are some mistakes we should be careful about:

Incorrect Base Case Initialization:
- If we do not set the base case for dynamic programming correctly, we can get wrong lengths for subsequences. We need to make sure that the first element of the LIS array starts at 1. Every single element is an increasing subsequence of length 1.
```
int[] lis = new int[n];
Arrays.fill(lis, 1);
```
Neglecting Edge Cases:
- We must think about edge cases. These include an empty array or an array with just one element. Not checking these can cause runtime errors. So, we should always check the input size before we start.
```
if not nums:
    return 0
```

Improper Nested Loops:

When we use a nested loop to compare elements, we need to compare the right indices. The outer loop should go through each element. The inner loop should check all previous elements.

for (int i = 1; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j]) {
            lis[i] = max(lis[i], lis[j] + 1);
        }
    }
}

Forgetting to Update the Maximum Length:
- After we build the LIS array, we must find the maximum value in the array. This maximum value shows the length of the longest increasing subsequence.
```
int maxLength = 0;
for (int length : lis) {
    maxLength = Math.max(maxLength, length);
}
```
Ignoring Space Complexity:
- If space complexity is important, we should not use a full DP array. We can think about using a temporary array or binary search with a list. This can help us get O(n log n) complexity.
Not Utilizing Binary Search:
- If we do not use binary search, our solution can be less efficient. We might end up with O(n^2) instead of O(n log n). We can use libraries like java.util.Arrays or bisect in Python for faster searching.
Improperly Handling Duplicates:
- Duplicates can make the LIS logic tricky. We need to handle them right. The definition of an increasing subsequence does not allow equal elements.
Lack of Testing:
- If we do not test the algorithm with different input cases, we might miss errors. We should always run tests with various scenarios to check our solution.

By avoiding these mistakes in the Longest Increasing Subsequence problem, we can make our implementation stronger and faster. If we want to read more on dynamic programming and related algorithms, we can check articles on Dynamic Programming - Fibonacci Number or Dynamic Programming - Coin Change.

Frequently Asked Questions

1. What is the time complexity of the Longest Increasing Subsequence algorithm?

The time complexity of the Longest Increasing Subsequence (LIS) algorithm can change based on the method we use. The dynamic programming method usually has a time complexity of O(n²). Here, n is the length of the input array. But if we use a mix of dynamic programming and binary search, we can lower the time complexity to O(n log n). This makes it better for bigger datasets.

2. How does the dynamic programming method find the Longest Increasing Subsequence?

The dynamic programming method finds the Longest Increasing Subsequence by making an array that keeps the length of the LIS at each index. For every element in the array, it looks at all the elements before it. Then it updates the LIS length based on the values we computed before. This way, we consider all possible increasing subsequences. In the end, we get the maximum length.

3. Can the Longest Increasing Subsequence algorithm handle duplicates?

Yes, the Longest Increasing Subsequence algorithm can deal with duplicates. When we find the LIS, we can include duplicate values in the subsequence as long as they keep the increasing order. But we need to make sure that we treat each occurrence right. This is especially important in dynamic programming methods where we compare indices.

4. What are some common mistakes when implementing the Longest Increasing Subsequence?

We can make some common mistakes when we implement the Longest Increasing Subsequence. One mistake is not starting the dynamic programming array right. Another mistake is messing up index comparisons. Also, we should not forget about edge cases like arrays that have all the same elements or arrays that just have one element. These can give us wrong results. It is very important to test with different input cases to avoid these problems.

5. How can I optimize space complexity in the Longest Increasing Subsequence problem?

To make space complexity better in the Longest Increasing Subsequence problem, we can lower the extra space used by the dynamic programming array from O(n) to O(1). We do this by only keeping the current and previous states of the LIS lengths instead of keeping a full array. Also, using binary search to update the LIS length can help us be more efficient and use less space.

For more insights on dynamic programming techniques, check our articles on Dynamic Programming: Fibonacci Number and Dynamic Programming: Minimum Path Sum in a Grid.