Skip to content

README.md

Latest commit

 

History

History
115 lines (89 loc) · 3.87 KB

README.md

File metadata and controls

115 lines (89 loc) · 3.87 KB

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:

  • Could you come up with the O(n2) solution?
  • Could you improve it to O(n log(n)) time complexity?

Related Topics:
Binary Search, Dynamic Programming

Similar Questions:

Solution 1. DP

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

// 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

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

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

If such v[i] exists, we replace v[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 v, we can simply append n into v.

// 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.