给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

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

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

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

提示：

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

进阶：

你可以设计时间复杂度为 O(n2) 的解决方案吗？
你能将算法的时间复杂度降低到 O(n log(n)) 吗?

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

解法

方法一：暴力dp, 定义dp[i] 表示到i位置的数字的最长递增子序列长度，dp[i] = dp[0...i-1] 里面的最大值+1
方法二： 排队法，把数组中的数字分队，数字比队头小或者等于则入队，否则新开一条队伍。

代码

• go

func m_max(a, b int) int {var res intif a > b {res = a} else {res = b}return res
}
func lengthOfLIS(nums []int) int {le := len(nums)dp := make([]int, le+1)var ans intans = 1for i := 0; i < le; i++ {dp[i] = 1for j := 0; j < i; j++ {if nums[i] > nums[j] {dp[i] = m_max(dp[i], dp[j]+1)ans = m_max(ans, dp[i])}}}return ans
}

• js

/*** @param {number[]} nums* @return {number}*/
var lengthOfLIS = function(nums) {let dp = [], ans = 1;let l = nums.length;for(let i=0; i<l; ++i ) dp[i] = 1;for(let i=0; i<l; ++i){for(let j=0; j<i; ++j){if( nums[j]<nums[i] ){dp[i] = Math.max( dp[i], dp[j]+1 );ans = Math.max(ans, dp[i])}}}return ans;
};

• c++

class Solution {
public:inline int m_max(int a, int b){return a>b?a:b;}int lengthOfLIS(vector<int>& nums) {int len = nums.size();// vector<int> dp;       // dp[i] 表示第i位最长增长子序列// for(int i=0; i<len+5; i++) dp.push_back(1);// int ans = 1;// for(int i=1; i<len; i++){//     for(int j=0; j<i; j++ ){//         if(nums[j] < nums[i]){//             // 如果j<i,则判断是否需要更新dp//             dp[i] = m_max(dp[i], dp[j]+1);//             ans = m_max(dp[i], ans);//         }//     }// }// return ans;/************ 上面是传统的递归，下面使用分堆法  ***********/vector<int> vec;int flag = 0;       // 0 表示当前数字还没分堆for(int i=0; i<len; i++){flag = 0;for(int j=0, l=vec.size(); j<l; j++){if(vec[j] >= nums[i]){vec[j] = nums[i];flag = 1;break;}}if(flag==0){// 找不到堆就新建vec.push_back(nums[i]);}}return vec.size();}
};