3、子数组必须连续，子序列可以不连续
算法原理：
1、状态表示（经验+题目要求）
dp[i]表示以i位置为结尾所有子系列中，最长递增子序列的长度。
2、状态转移方程
（1）长度为1——>dp[i]=1
(2)长度大于1——>满足前提（nums[j]
3、初始化
如果无法更新，最差情况自己也是一个子序列，所以dp表全都初始化为1
4、填表顺序
需要借助前面的状态，所以要从左往右
5、返回值
dp表中的最大值——>可以用ret去更新出最大值，也可以用*max_element(dp.begin(),dp.end())
6、复杂度
空间复杂度：N
dp[i]表示以i位置为结尾所有子序列中，最长递增子序列的长度。（错误）
因为会存在两种状态，所以我们需要两个dp数组：
f[i]表示以i位置为结尾的所有子序列中，最后一个位置呈现“上升”趋势的最长摆动序列的长度
g[i]表示以i位置为结尾的所有子序列中，最后一个位置呈现“下降”趋势的最长摆动序列的长度
f[i]（上升）:
（1）长度为1——>1
(2)长度大于1——>满足前提（nums[j]
g[i]（下降）:
(2)长度大于1——>满足前提（nums[j]>nums[i]）——>max(f[j]+1,g[i])（0<=j<=i-1）
如果无法更新，最差情况自己也是一个子序列，所以g表和f表全都初始化为1
需要借助前面的状态，所以要从左往右，两个表一起填
两个表中的最大值
在讲解前先来个小demo：如何在数组中找出最大值出现的次数
方案1：第一次for循环确定最大的值是多少，第二次for循环统计最大的值出现了几次
方案2：利用贪心策略一次for循环搞定（定义maxval记录当前的最大值，count统计数量）
（1）x==maxval:++count
（2）x （3）x>maxval:更新最大值——>maxval=x，然后重新计数——>count=1 dp[i]表示以i位置为结尾所有子序列中，最长递增子序列的个数。（错误） 因为我们在填表的时候并不能确认最长递增子序列的长度是多少，所以无法直接统计。我们就得用demo中的方案2的思想，来解决这个问题。 len[i]表示以i位置为结尾的所有子序列中，最长递增子序列的“长度” count[i]表示以i位置为结尾的所有子序列中，最长递增子序列的“个数” nums[j] （1）len[j]+1==len[i]——>count[i]+=count[j] （2）len[j]+1 （3）len[j]+1>len[i]——>len[i]=len[j]+1count[i]=count[j]（更新最大值并重新计数） 全都初始化为1 recount统计结果 预处理：由于题目要求是任意顺序组成数链对，所以我们在处理的时候不仅要考虑前面，还要考虑后面，这样不利于我们的动态规划表示，所以我们要先按照第一个元素进行排序(比如[a,b][c,d]，a dp[i]表示以i位置为结尾所有数对链序列中，最长数对链的长度。 dp[i]: (1)长度为1——1 (2)长度大于1——p[j][1]>p[i][0]——max(dp[i],dp[j]+1) 初始化为1 要返回dp表中的最大值，但由于我们排序过，所以最大值必然出现在dp[n-1]。 dp[i]表示以i位置为结尾所有子序列中，最长的等差子序列长度 (1)b不存在——>1 (2)b存在——>取最后一个即可dp[j]+1 我们会发现前一个数基本上是可以确定是多少的，并且有多个的话也可以用后面的覆盖前面的，因此我们可以用哈希表做优化 优化思路： （1)将元素+dp[i]的值存在哈希表中 （2)直接在哈希表中做动态规划 hash[arr[0]]=1 从左往右 dp表里的最大值 dp[i]表示以i位置为结尾所有子序列中，最长的斐波那契子序列长度（错误）。 因为我们至少得确定两个位置，才能知道序列是否满足斐波那契子序列的要求。 dp[i][j]表示以i位置及j位置为结尾所有子序列中，最长的斐波那契子序列长度。 dp[i][j]:（假设abc对应的坐标分别是kij） (1)如果a存在且a (2)a存在且b (3)a不存在——>2 优化思路：将元素与下标绑定存放在哈希表中。 都初始化为2 dp表里的最大值ret但是如果ret是2的话就返回0 dp[i]表示以i位置为结尾所有子序列中，最长的等差子序列的长度（错误）。 因为我们至少得确定两个位置，才能知道序列是否满足等差子序列的要求。 dp[i][j]表示以i位置及j位置为结尾所有子序列中，最长的等差子序列长度。 （1）将元素与下标绑定存放在哈希表中。 （2）i位置填完后，将i位置的值放进哈希表中 有两种方式（选择方法2） （1）先固定最后一个数，然后枚举倒数第二个数（必须在dp前先将元素与下标的关系绑定再哈希表中，到时候在找的时候还得判断b （2）先固定倒数第二个数，再枚举最后一个数（可以等i位置填完后再将i的位置丢进哈希表，这样可以保证哈希表内的元素的下标必然是小的，就可以不需要判断b dp表里的最大值ret (1)如果a存在且a (2)a存在且b (3)a不存在——>0 （1）将元素与下标绑定存放在哈希表中。（该题需要统计所有的子序列，所以相同元素下标不同的情况都要统计，因此我们要将元素绑定一个下标数组） 都初始化为0 先固定倒数第二个数，再枚举最后一个数（可以等i位置填完后再将i的位置丢进哈希表，这样可以保证哈希表内的元素的下标必然是小的，就可以不需要判断b