300. Longest Increasing Subsequence

300. Longest Increasing Subsequence (Medium)

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

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

 

Example 1:

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.

Example 2:

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

Example 3:

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

 

Constraints:

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

 

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Companies:
Google, Microsoft, Amazon, Twitter, Apple, Bloomberg, Splunk, MakeMyTrip, ServiceNow, Samsung

Related Topics:
Array, Binary Search, Dynamic Programming

Similar Questions:

• Increasing Triplet Subsequence (Medium)
• Russian Doll Envelopes (Hard)
• Maximum Length of Pair Chain (Medium)
• Number of Longest Increasing Subsequence (Medium)
• Minimum ASCII Delete Sum for Two Strings (Medium)
• Minimum Number of Removals to Make Mountain Array (Hard)
• Find the Longest Valid Obstacle Course at Each Position (Hard)

Solution 1. DP

Let dp[i] be the length of the LIS ending at A[i].

For dp[i], we can try each dp[j] before A[i] by appending A[i] to the LIS represented by dp[j] (0 <= j < i && A[j] < A[i])

dp[i] = min(1, max( dp[j] + 1 | 0 <= j < i && A[j] < A[i] ))

// OJ: https://leetcode.com/problems/longest-increasing-subsequence/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
    int lengthOfLIS(vector<int>& A) {
        if (A.empty()) return 0;
        int N = A.size();
        vector<int> dp(N, 1);
        for (int i = 1; i < N; ++i) {
            for (int j = 0; j < i; ++j) {
                if (A[j] < A[i]) dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        return *max_element(begin(dp), end(dp));
    }
};

Solution 2. Binary Search (Regret Greedy)

We use a vector<int> lis to store the LIS. lis is always sorted.

For each n in A, we first find the first lis[i] that is >= n.

If such lis[i] exists, we replace lis[i] with n. Such operation won't break the LIS but make this LIS easier to extend.

Otherwise, n is greater than all values in lis, we can simply append n into lis.

// OJ: https://leetcode.com/problems/longest-increasing-subsequence/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
// Ref: https://leetcode.com/problems/longest-increasing-subsequence/solution/
class Solution {
public:
    int lengthOfLIS(vector<int>& A) {
        vector<int> v;
        for (int n : A) {
            auto i = lower_bound(begin(v), end(v), n);
            if (i == end(v)) v.push_back(n);
            else *i = n;
        }
        return v.size();
    }
};

Note

1671. Minimum Number of Removals to Make Mountain Array (Hard) is a great bidirectional extension of this problem.