目录
最长递增子序列
题解：
代码：
递增的三元子序列
题解：
代码：
简易版：
最长连续递增序列
题解：
代码：
最长递增子序列
300. 最长递增子序列 - 力扣（LeetCode）https://leetcode.cn/problems/longest-increasing-subsequence/description/
题解：
如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。
以数组 nums = [ 7, 3, 8, 4, 7, 2, 14, 13 ] 为例，从下标为 0 位置开始遍历：
当访问 nums[ 0 ] 时，此时长度为 1 的子序列的元素为 7；
当访问 nums[ 1 ] 时，由于 3 < 7，所以 7 和 3 无法构成递增子序列，所以长度为 1 的子序列的元素为 3 或者 7，此时长度为 1 的子序列的元素应该保留 3，去掉 7，原因如下：假如再来一个元素 x，
- 如果 x > 7，此时长度为 2 的子序列有两种可能，[ 3, x ] 或者 [ 7, x ] ；
- 如果 3 < x <= 7，那么长度为 2 的子序列只有 [ 3, x ] 一种情况。
也就是说，能与 7 构成递增子序列的元素，也一定可以与 3 构成递增子序列，但能与 3 构成递增子序列的元素不一定可以与 7 构成递增子序列，所以保留 3 去掉 7 可以让递增子序列的长度尽可能长！此时长度为 1 的子序列的最后一个元素为 3.
当访问 nums[ 2 ] 时，8 可以和 3 构成递增子序列，此时长度为 1 的子序列的最后一个元素为 3，长度为 2 的子序列的最后一个元素为 8.
当访问 nums[ 3 ] 时，4 比 8 小，而且 4 比长度为 1 的子序列的最后一个元素 3 大，此时长度为 2 的子序列有两种情况，[ 3, 4 ] 或者 [ 3, 8 ] ，和上面同理，能与 [ 3, 8 ] 构成递增子序列的元素，也可以与 [ 3, 4 ] 构成递增子序列，但能与 [ 3, 4 ] 构成递增子序列的元素，不一定能与 [ 3, 8 ] 构成递增子序列。所以长度为 2 的子序列的最后一个元素更新为 4.
当访问 nums[ 4 ] 时，7 比 4 大，可以与 [ 3, 4 ] 构成递增子序列，此时长度为 3 的子序列的最后一个元素为 7。
当访问 nums[ 5 ] 时，2 比 3 小，和上面同理，长度为 1 的子序列的最后一个元素更新为 2.
当访问 nums[ 6 ] 时，14 比 7 大，可以构成递增子序列，此时长度为 4 的子序列的最后一个元素为 14。
当访问 nums[ 7 ] 时，13 比 14 小，但比 7 大，此时长度为 4 的子序列的最后一个元素为 14。
从上述过程可以看出，假设用数组 ret 来保存长度为 x 的子序列的最后一个元素，当前数组的长度为 n：
- 当前遍历到的元素 a 比 当前长度最长的子序列的最后一个元素大时， 即 a 大于数组的最后一个元素，则递增子序列的长度+1，即数组 ret 的长度 n++，且 ret [ n ] = a；
- 当前遍历到的元素 a 比 当前长度最长的子序列的最后一个元素小时，则需要在数组中找到大于等于 a 的数中的最小值，然后用 a 把这个数覆盖掉。
思想就是让 ret 中存储比较小的元素。这样，ret 未必是真实的最长上升子序列，但长度是对的，只能说明我们曾经得到过这一长度的递增子序列。
如何快速在数组中找到大于等于 a 的数中的最小值？
用二分查找思想，根据数组元素的更新策略，可以看出数组中的元素是递增的，假设在数组中第一个大于等于 a 的数的下标为 i，数组的长度为 n，那么数组可以被划分为两部分，下标范围为 [ 0, i-1 ] 的数都比 a 小，下标范围为 [ i , n-1 ] 的数都大于等于 a，此二段性可以帮助我们快速定位要把元素 a 放在哪里。
代码：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> ret;
ret.push_back(nums[0]);
int n=nums.size();
for(int i=1;i<n;i++)
{
int x=nums[i];
if(x>ret.back())
{
ret.push_back(x);
}
else
{
int left=0,right=ret.size()-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(ret[mid]<x) left=mid+1;
else right=mid;
}
ret[left]=x;
}
}
return ret.size();
}
};递增的三元子序列
334. 递增的三元子序列 - 力扣（LeetCode）https://leetcode.cn/problems/increasing-triplet-subsequence/description/
题解：
和上一题同理，如果 ret 数组的长度为 3，说明存在递增的三元子序列，此时直接返回 true 即可。
代码：
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
vector<int> ret;
ret.push_back(nums[0]);
int n=nums.size();
for(int i=1;i<n;i++)
{
if(nums[i]>ret.back())
{
ret.push_back(nums[i]);
if(ret.size()==3)
return true;
}
else
{
int left=0,right=ret.size()-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(ret[mid]<nums[i]) left=mid+1;
else right=mid;
}
ret[left]=nums[i];
}
}
return false;
}
};简易版：
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int first=nums[0],second=INT_MAX;
for(int i=0;i<nums.size();i++)
{
if(nums[i]>second) return true;
else if(nums[i]>first) second=nums[i];
else first=nums[i];
}
return false;
}
};最长连续递增序列
674. 最长连续递增序列 - 力扣（LeetCode）https://leetcode.cn/problems/longest-continuous-increasing-subsequence/description/
题解：
本题其实是一个滑动窗口。注意窗口不要越界，且窗口左闭右开。left 是窗口的左端点，right 是窗口的右端点。
代码：
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int left=0,right=0,n=nums.size(),ret=0;
while(left<n)
{
right=left+1;
while(right<n && nums[right]>nums[right-1])
right++;
ret=max(ret,right-left);//左闭右开
left=right;
}
return ret;
}
};