300. Longest Increasing Subsequence

2021, Mar 04 2 mins read

1. Description

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

2. Example

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

3. Constraints

1 <= nums.length <= 2500
-10$^{4}$ <= nums[i] <= 10$^{4}$

4. Solutions

Dynamic Programming

n = nums.size()
Time complexity: O($n^2$)
Space complexity: O(n)

class Solution {
public:
    int lengthOfLIS(const vector<int> &nums) {
        const int n = nums.size();
        vector<int> length_end_at(n, 1);
        int max_length = 1;
        for (int i = 1; i < n; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                if (nums[i] > nums[j]) {
                    length_end_at[i] = max(length_end_at[j] + 1, length_end_at[i]);
                }

                if (length_end_at[i] == i + 1) {
                    break;
                }
            }

            max_length = max(length_end_at[i], max_length);
        }

        return max_length;
    }
};

Dynamic Programming && Binary Search

n = nums.size()
Time complexity: O(nlogn)
Space complexity: O(n)

class Solution {
public:
    int lengthOfLIS(const vector<int> &nums) {
        const int n = nums.size();
        vector<int> len_min_end_value;
        len_min_end_value.reserve(n);
        for (int num : nums) {
            auto iter = lower_bound(len_min_end_value.begin(), len_min_end_value.end(), num);
            if (iter == len_min_end_value.end()) {
                len_min_end_value.push_back(num);
            } else {
                *iter = num;
            }
        }

        return len_min_end_value.size();
    }
};