给你一个整数数组 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 int if a > b { res = a } else { res = b } return res } func lengthOfLIS(nums []int) int { le := len(nums) dp := make([]int, le+1) var ans int ans = 1 for i := 0; i < le; i++ { dp[i] = 1 for 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(); } };
