1
2
3

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

1
2

输入：nums = [0,1,0,3,2,3]
输出：4

1
2

输入：nums = [7,7,7,7,7,7,7]
输出：1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 动态规划
    /// 1. 设dp[i]: 表示以nums[i]为尾的最长递增序列的长度
    /// 2. 递推关系: dp[i] = max(dp[j]) + 1 (0=<j<i, nums[j]<nums[i])
    /// 3. 初始条件: dp[i] = 1 (i=0..n-1)
    /// 4. 目标: dp[nums.len()-1]
    pub fn length_of_lis0(nums: Vec<i32>) -> i32 {
        let mut dp = vec![1; nums.len()];
        let mut res = 1;
        for i in 1..nums.len() {
            for j in 0..i {
                if nums[i] > nums[j] {
                    dp[i] = dp[i].max(dp[j] + 1);
                }
            }
            res = res.max(dp[i] as i32);
        }

        res
    }

    /// ## 解题思路2
    /// - 贪心+二分查找
    /// 1. 设 lis[i]: nums[0..i]的最长递增子序列;
    /// 2. 初始化 lis[0] = nums[0];
    /// 3. 从左至右, 依次遍历nums[1..]
    /// 4. 如果 nums[i] > lis.last(), 则将nums[i]加入到lis[]末尾;
    /// 5. 否则, nums[i] < lis.last(),
    ///    在lis[]中查找第一个大于nums[i]的数lis[j](0=<j<i), 将其替换为nums[i];
    /// 6. 由于lis[]为递增序列, 则可使用二分法快速查找lis[j]
    pub fn length_of_lis(nums: Vec<i32>) -> i32 {
        let mut lis = vec![]; //最长递增子序列
        for n in nums {
            match lis.last() {
                None => lis.push(n),
                Some(&l) if l < n => lis.push(n),
                _ => match lis.binary_search(&n) {
                    Err(j) => lis[j] = n,
                    _ => {}
                },
            }
        }

        return lis.len() as i32;
    }
}
// @lc code=end

struct Solution;
#[cfg(test)]
mod tests {
    use super::*;

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