DP--最长递增子序列的个数（线性-单串）

目录

题目

思路

    状态定义

        dp[i]表示以i结尾的最长递增序列的长度

        知道了最长递增序列后，则下一次再在同等长度的序列中发现等长的，加一，则完成了在dp[i]范围上最长个数的收集

    转义方程

        求dp[i]时，dp[0]到dp[i-1]的最长序列长度和与最长序列长度等长的个数已经被收集

        想要得到更长的序列，需要nums[i]比nums[0]到nums[i]的最大值还大

        即i依赖比i小的O(n)的子问题

        故状态转移方程如下

                dp[i] = max(dp[0].......dp[i-1])+1

    边界

        nums[i]>nums[j] 0<=j<i

实现

（如果dp[j]+1==dp[i]则nums[j]一定小于nums[i]且小于nums[j-1]，说明在下标j处出现拐点可以组合出更多的序列个数,事实上，每出现一个拐点则会在原组合基础上翻一倍；由于新数的加入不会影响组合个数，故可以直接继承maxLensAtI[j]）