673. 最长递增子序列的个数

题目描述给定一个未排序的整数数组numsnumsnums 返回最长递增子序列的个数 。注意这个数列必须是严格递增的。示例 1:输入: [1,3,5,4,7]输出: 2解释: 有两个最长递增子序列分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。示例 2:输入: [2,2,2,2,2]输出: 5解释: 最长递增子序列的长度是1并且存在5个子序列的长度为1因此输出5。算法原理前置算法假设现在有一个数组nums[2,3,1,2,3]nums [2, 3, 1, 2, 3]nums[2,3,1,2,3]要求一次遍历求出这个数组中最大值的出现次数怎么做呢可以设置两个变量mmm和cntcntcntmmm用来记录最大值cntcntcnt用来记录最大值的出现次数初始化mnums[0]cnt1m nums[0]cnt1mnums[0]cnt1从左到右遍历numsnumsnums遍历时nums[i]mnums[i] mnums[i]m说明nums[i]nums[i]nums[i]不可能是最大值什么也不做nums[i]mnums[i] mnums[i]m说明nums[i]nums[i]nums[i]是假定的最大值cntcntcntnums[i]mnums[i] mnums[i]m说明nums[i]nums[i]nums[i]更大是可能的最大值更新mnums[i],cnt1m nums[i], cnt 1mnums[i],cnt1当遍历完时mmm就保存了最大值cntcntcnt就保存了最大值的出现次数动态规划状态表示子序列问题一般以经验题目要求得到经验就是以某一个位置为结尾题目要求就是最长递增子序列的个数所以count[i]count[i]count[i]表示以iii位置为结尾的所有子序列中最长递增子序列的个数。由于不知道最长递增子序列长度所以根本求不了个数所以还需要一个数组lenlenlenlen[i]len[i]len[i]表示以iii位置为结尾的所有子序列中最长递增子序列的长度。状态表示可总结为count[i]count[i]count[i]以iii位置为结尾的所有子序列中最长递增子序列的个数len[i]len[i]len[i]以iii位置为结尾的所有子序列中最长递增子序列的长度状态转移方程以iii位置为结尾的子序列可以分为长度1 11和长度1 11的。根据前置算法可以同时填count,lencount, lencount,len两个表对于长度1 11的子序列最长递增子序列只有它自己所以len[i]1,count[i]1len[i] 1, count[i] 1len[i]1,count[i]1对于长度1 11的子序列一般是以i−1,i−2,...,0i-1, i-2, ..., 0i−1,i−2,...,0位置元素为结尾的最长递增子序列再带上iii位置上的元素。假设0ji−10 j i-10ji−1如果nums[j]nums[i]nums[j] nums[i]nums[j]nums[i]说明iii位置元素可以跟在以jjj位置元素为结尾的最长递增子序列之后此时新最长递增子序列的长度就是以jjj位置元素为结尾的最长递增子序列长度1 11也就是len[j]1len[j] 1len[j]1。如果len[j]1len[i]len[j] 1 len[i]len[j]1len[i]说明又出现了一个可能的最长递增子序列统计最长递增子序列的个数count[i]count[j]count[i] count[j]count[i]count[j]。如果len[j]1len[i]len[j] 1 len[i]len[j]1len[i]说明不可能是最长递增子序列此时啥也不做。如果len[j]1len[i]len[j] 1 len[i]len[j]1len[i]说明有更长的最长递增子序列更新len[i]len[j]1,count[i]count[j]len[i] len[j] 1, count[i] count[j]len[i]len[j]1,count[i]count[j]初始化以每个位置为结尾的最长递增子序列长度至少为111至少有111个所以初始化len,countlen, countlen,count为全111填表顺序从左到右返回值使用一次遍历的思想遍历len,countlen, countlen,count来找到最大的长度统计出现次数代码classSolution{public:intfindNumberOfLIS(vectorintnums){intnnums.size();vectorintlen(n,1),count(n,1);intmaxLenlen[0],cntcount[0];for(inti1;in;i){for(intji-1;j0;--j)// 找到以 [0, i-1] 结尾的递增子序列长度{if(nums[i]nums[j])// 能构成以 i 结尾的递增子序列{if(len[j]1len[i])// 当前递增子序列的长度 假定的最长递增子序列长度{count[i]count[j];// 更新最长递增子序列的个数}elseif(len[j]1len[i])// 当前递增子序列的长度 假定的最长递增子序列长度{len[i]len[j]1;// 更新最长递增子序列长度count[i]count[j];// 更新最长递增子序列的个数}}}if(len[i]maxLen){cntcount[i];}elseif(len[i]maxLen){maxLenlen[i];cntcount[i];}}returncnt;}};