Skip to content

Latest commit

 

History

History

300

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 

README.md

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, Amazon, Microsoft, Facebook, ByteDance, VMware, Apple, Adobe, Bloomberg, Walmart Labs, tiktok, HRT, TuSimple

Related Topics:
Array, Binary Search, Dynamic Programming

Similar Questions:

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();
    }
};

or doing it in-place

// OJ: https://leetcode.com/problems/longest-increasing-subsequence/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1) extra space
class Solution {
public:
    int lengthOfLIS(vector<int>& A) {
        int len = 0;
        for (int i = 0; i < A.size(); ++i) {
            int j = lower_bound(begin(A), begin(A) + len, A[i]) - begin(A);
            if (j == len) ++len;
            A[j] = A[i];
        }
        return len;
    }
};

Note

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