LeetCode 300. Longest Increasing Subsequence

Today we're going to solve LeetCode 300. Longest Increasing Subsequence

| Problem description

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

Examples:

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

| Concept

To solve this problem, we can use a vector sub to store the current longest increasing subsequence.

Then, we use a for loop to go through all elements in nums.

When num == empty, we add an element into our vector.

When we find an element that is smaller than the final element of sub, replace it.

Hint:

We can use C++ built-in lower_bound() function to find the lower bound number's pointer.

Continue the loop, we can get the longer increasing subsequence.

| Analyzed complexity:

Time complexity: O(n)
Space complexity: O(n)

| Code

class Solution {
  public:
      int lengthOfLIS(vector<int>& nums) {
          vector<int> sub; 
          for (int num : nums) {
              if (sub.empty() || sub[sub.size() - 1] < num) {
                  sub.push_back(num);
              } else {
                  auto iter = lower_bound(sub.begin(), sub.end(), num);
                  if (iter != sub.end()) *iter = num;
              }
          }
          return sub.size();
      }
  }