给你一个整数数组 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
这题应该是动态规划中最经典的题。同时也是面试中最经常出的题，主要有以下两种方法。
1.动态规划(O(N²))
1. 定义状态：
dp[i] 表示：以 nums[i] 结尾 的「上升子序列」的长度。
2. 状态转移方程：
只要 nums[i] 严格大于在它位置之前的某个数，那么 nums[i] 就可以接在这个数后面形成一个更长的上升子序列。
dp[i] = max(dp[i], dp[j] + 1); ( 0 < j < i )
3. 初始化：
个人觉得初始化这部分应该是最要纠结的边界问题了,这里有dp[i] = 1。
4.输出:
因为是要最长的，而不是求包括末尾的最长子序列，所以用一个maxnum保存每次的dp[i]即可。
5.代码
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
//O(n²)
int length = nums.size();
int maxnum = 1;
vector<int> dp(length, 1);
for(int i = 0; i < length; i++){
for(int j = 0; j < i; j++){
if(nums[i] > nums[j]){
dp[i] = max(dp[i], dp[j] + 1);
maxnum = max(maxnum,dp[i]);
}
}
}
return maxnum;
}
};
2.贪心 + 二分(O(NlogN))
动态规划也是暴力的解法，只不过他是把暴力之后的数据存储起来，对于这题来说可以用贪心 + 二分的方式做，能得到更低的复杂度。
1.在遍历数组 nums 的过程中，看到一个新数 num，如果这个数 严格 大于有序数组 tail 的最后一个元素，就把 num 放在有序数组 tail 的后面，否则进入第 2 点；
注意：这里的大于是「严格大于」，不包括等于的情况。
2.在有序数组 tail 中查找第 1 个等于大于 num 的那个数，试图让它变小；
如果有序数组 tail 中存在 等于 num 的元素，什么都不做，因为以 num 结尾的最短的「上升子序列」已经存在；
如果有序数组 tail 中存在 大于 num 的元素，找到第 1 个，让它变小，这样我们就找到了一个 结尾更小的相同长度的上升子序列。
在有序数组 tail 中查找第 1 个等于大于 num 的那个数，试图让它变小；
这里是引用liweiwei1419的话，他在原文中定义了一个新的状态，但是我其实觉得这个跟动态规划没什么关系。
举个例子：
10 9 2 5 3 7 这串数字要找最长上升序列
首先读入10 然后10 9 因为9比10小所以进入(2)替换10，所以数组tail变成9
然后读入2，2小于9，数组变成2，然后是
2 5
2 5 3(3小于5,进入(2)阶段然后代替第一个比3大的数5) -> 2 3
然后是 2 3 7
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
// O(nlogn)
int length = nums.size();
vector<int> tail;
tail.push_back(nums[0]);
for(int i = 1; i < length; i++){
if(nums[i] > tail.back()){
tail.push_back(nums[i]);
}
else{
// 大于等于
// tail 中第一个大于nums[i]的元素位置,考虑到有相等元素，不能用 upperboud !
vector<int>::iterator iter = lower_bound(tail.begin(),tail.end(),nums[i]);
*iter = nums[i];
}
}
return tail.size();
}
};
这种方法出来的上升子序列的数量一定是对的，但是他数组里面的数字不一定是对的。
|
