300.最长递增子序列
给你一个整数数组
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
dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值。
初始值大小至少是1，且从前往后遍历。
代码
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.size()<=1)return nums.size();
vector<int>dp(nums.size(),1);
int result=0;
for(int i=1;i<nums.size();i++)//背包
{
for(int j=0;j<i;j++)//在 i 之前查找比 nums[i] 小的元素 nums[j]。如果 nums[i] > nums[j]，说明 nums[i] 可以接在 nums[j] 后形成一个更长的递增子序列，所以更新 dp[i] 为 dp[j] + 1，并取 dp[i] 和 dp[j] + 1 的最大值，保证 dp[i] 是最大的递增子序列长度。
{
if(nums[i]>nums[j])dp[i]=max(dp[i],dp[j]+1);
}
if(dp[i]>result)result=dp[i];//更新每一段0到i的最大递增子序列
}
return result;
}
};674. 最长连续递增序列
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标
l和r（l < r）确定，如果对于每个l <= i < r，都有nums[i] < nums[i + 1]，那么子序列[nums[l], nums[l + 1], ..., nums[r - 1], nums[r]]就是连续递增子序列。示例 1：
输入：nums = [1,3,5,4,7] 输出：3 解释：最长连续递增序列是 [1,3,5], 长度为3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。示例 2：
输入：nums = [2,2,2,2,2] 输出：1 解释：最长连续递增序列是 [2], 长度为1。
dp思路。
dp[i]：以下标i为结尾的连续递增的子序列长度为dp[i]。
如果 nums[i] > nums[i - 1]，那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 + 1 。
即：dp[i] = dp[i - 1] + 1;
代码
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
if(nums.size()<=1)return nums.size();
vector<int>dp(nums.size(),1);
int result=0;
for(int i=1;i<nums.size();i++)
{
if(nums[i]>nums[i-1])
dp[i]=dp[i-1]+1;
if(dp[i]>result)result=dp[i];
}
return result;
}
};本题很简单，用贪心思路也差不多。
718.最长重复子数组
给两个整数数组
nums1和nums2，返回 两个数组中 公共的 、长度最长的子数组的长度 。示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] 输出：3 解释：长度最长的公共子数组是 [3,2,1] 。示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] 输出：5
思路
难在是有两个数组，需要同时遍历取公共的最长子数组的长度。
dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。
即当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1;
根据dp[i][j]的定义，dp[i][0] 和dp[0][j]其实都是没有意义的！
但dp[i][0] 和dp[0][j]要初始值，因为 为了方便递归公式dp[i][j] = dp[i - 1][j - 1] + 1;
所以dp[i][0] 和dp[0][j]初始化为0。
遍历顺序，从小到大，但两个数组谁在外面就没有讲究了。
代码
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
//创建了一个二维数组 dp，用于记录相同位置的公共子数组的长度。dp[i][j] 表示 nums1 的前 i 个元素和 nums2 的前 j 个元素所能形成的最长公共子数组的长度。额外增加的 1 个行和列是为了处理边界情况，便于代码编写
vector<vector<int>>dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
int result=0;//存储最长公共子数组的最大长度
for(int i=1;i<=nums1.size();i++)//先遍历一个数组，直到第二个数组找到相同元素
{
for(int j=1;j<=nums2.size();j++)
{
//表明在当前位置上有一个公共元素。令 dp[i][j] = dp[i - 1][j - 1] + 1，即当前匹配的公共子数组长度等于前一位置的公共子数组长度加 1。如果不相等，dp[i][j] 保持为初始值 0。
if(nums1[i-1]==nums2[j-1])
dp[i][j]=dp[i-1][j-1]+1;//如果相等，则在对应的二维数组位置（也可以理解为坐标）
if(dp[i][j]>result)result=dp[i][j];
}
}
return result;
}
};