Longest Increasing Subsequence in C++ | Time Complexity: O(n log n)

Problem Definition

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Input: An array of integers nums.

Output: An integer representing the length of the longest increasing subsequence.

Constraints:

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

Example:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Understanding the Problem

The core challenge of this problem is to find the longest subsequence in the array where each element is greater than the previous one. This problem is significant in various fields such as bioinformatics, computer vision, and more, where finding patterns in sequences is crucial.

Common pitfalls include misunderstanding the definition of a subsequence (which does not require contiguous elements) and confusing it with subarrays.

Approach

To solve this problem, we can start with a naive approach and then move to more optimized solutions.

Naive Solution

The naive solution involves generating all possible subsequences and checking each one to see if it is increasing. This approach is not feasible due to its exponential time complexity.

Dynamic Programming Solution

A better approach is to use dynamic programming. We can maintain an array dp where dp[i] represents the length of the longest increasing subsequence that ends with nums[i]. The time complexity of this approach is O(n^2).

Optimized Solution with Binary Search

The most optimized solution uses a combination of dynamic programming and binary search. We maintain an array tails where tails[i] is the smallest possible tail value for all increasing subsequences of length i+1. The time complexity of this approach is O(n log n).

Algorithm

Dynamic Programming Solution

1. Initialize a dp array with all elements set to 1.
2. For each element nums[i], iterate through all previous elements nums[j] (where j < i).
3. If nums[i] > nums[j], update dp[i] to be the maximum of dp[i] and dp[j] + 1.
4. Return the maximum value in the dp array.

Optimized Solution with Binary Search

1. Initialize an empty array tails.
2. For each element num in nums, use binary search to find the position in tails where num can replace the existing value or be appended.
3. If num is larger than all elements in tails, append it to tails. Otherwise, replace the element at the found position.
4. Return the length of the tails array.

Code Implementation

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

using namespace std;

// Dynamic Programming Solution
int lengthOfLIS_DP(vector<int>& nums) {
    if (nums.empty()) return 0;
    vector<int> dp(nums.size(), 1);
    int maxLength = 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);
            }
        }
        maxLength = max(maxLength, dp[i]);
    }
    return maxLength;
}

// Optimized Solution with Binary Search
int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    return tails.size();
}

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

Complexity Analysis

Dynamic Programming Solution:

• Time Complexity: O(n^2) due to the nested loops.
• Space Complexity: O(n) for the dp array.

Optimized Solution with Binary Search:

• Time Complexity: O(n log n) due to the binary search operations.
• Space Complexity: O(n) for the tails array.

Edge Cases

Consider the following edge cases:

• An empty array should return 0.
• An array with all identical elements should return 1.
• An array with elements in strictly decreasing order should return 1.

Examples:

Input: nums = []
Output: 0

Input: nums = [5, 5, 5, 5]
Output: 1

Input: nums = [5, 4, 3, 2, 1]
Output: 1

Testing

To test the solution comprehensively, consider the following test cases:

• Simple cases with small arrays.
• Arrays with all elements the same.
• Arrays with elements in strictly increasing or decreasing order.
• Large arrays to test performance.

Example test cases:

vector<int> test1 = {1, 2, 3, 4, 5}; // Expected output: 5
vector<int> test2 = {5, 4, 3, 2, 1}; // Expected output: 1
vector<int> test3 = {2, 2, 2, 2}; // Expected output: 1
vector<int> test4 = {10, 9, 2, 5, 3, 7, 101, 18}; // Expected output: 4

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

• Understand the problem requirements and constraints thoroughly.
• Start with a brute-force solution to understand the problem better.
• Look for patterns and use dynamic programming to optimize.
• Consider advanced data structures like binary search to further optimize.
• Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to solve the problem of finding the longest increasing subsequence in an array using C++. We covered the problem definition, various approaches, detailed algorithms, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving algorithmic thinking and coding skills.

We encourage you to practice and explore further to deepen your understanding.

Additional Resources

• LeetCode Problem
• GeeksforGeeks Article
• TopCoder Dynamic Programming Tutorial