673. 最長遞增子序列的個數

給定一個未排序的整數數組?nums?，?返回最長遞增子序列的個數?。

注意?這個數列必須是?嚴格?遞增的。

思路：

用一個maxlen表示當前最長遞增數組的長度，maxcount表示最大長度。當進下標為i的元素時，將其和j（0-i-1）之間的元素比較，若大小大于num[j]，則由包含j的最大子序列加i仍可能是最大子序列，此時判斷當前包含i的最大長度和由j加上i元素的最大長度比較，若大于則更新最大長度和數量（因為此時相當于找了一個更大的來做最長子序列，因此都需要重新計算），若小于則忽略，若等于則數量相加。

再遍歷完（0-i-1）后，要更新maxlen和maxcount，若當前的maxlen等于len[i]，則表示以i位置結尾的最大長度和（0-i-1）中某個最大長度一致，則maxcount等于count[i]+maxcount，若maxlen小于len[i]，則maxlen更新，maxcount更新。若maxlen大于len[i]，則表示最長不是包含i的，則不變。

就是一次更新是只看當前i位置的len和count，一次比較是求（0-i）里的最大len和最大count。

class Solution {
public:int findNumberOfLIS(vector<int>& nums) {int n=nums.size();vector<int>len(n,1);//   len[0]=1;vector<int>count(n,1);//count[0]=1;int retlen=1,retcount=1;for(int i=1;i<n;i++){for(int j=0;j<i;j++){if(nums[i]>nums[j]){if(len[i]<len[j]+1){len[i]=len[j]+1;count[i]=count[j];}else if(len[i]==len[j]+1){count[i]+=count[j];}}}if(retlen==len[i]){retcount+=count[i];}else if(retlen<len[i]){retcount=count[i];retlen=len[i];}}return retcount;}
};