300. Longest Increasing Subsequence

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

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?

Solutions (Rust)

1. Solution

impl Solution {
    pub fn length_of_lis(nums: Vec<i32>) -> i32 {
        let mut stack = vec![-10001];

        for &num in &nums {
            if num > *stack.last().unwrap() {
                stack.push(num);
            } else if let Err(i) = stack.binary_search(&num) {
                stack[i] = num;
            }
        }

        stack.len() as i32 - 1
    }
}