300. Longest Increasing Subsequence

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?

300. Longest Increasing Subsequence
struct Solution;

impl Solution {
    fn length_of_lis(nums: Vec<i32>) -> i32 {
        let mut dp: Vec<i32> = vec![];
        for x in nums {
            if let Err(i) = dp.binary_search(&x) {
                if i == dp.len() {
                    dp.push(x)
                } else {
                    dp[i] = x;
                }
            }
        }
        dp.len() as i32
    }
}

#[test]
fn test() {
    let nums = vec![10, 9, 2, 5, 3, 7, 101, 18];
    let res = 4;
    assert_eq!(Solution::length_of_lis(nums), res);
}