描述
给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。
分析
在最长子序列的基础上求最长上升序列的个数。一个数组记录以当前元素的为结尾的最长上升子序列的长度，另一个记录最长上升子序列的个数，最后得出最长子序列的个数。
在计算当前元素的最长上升子序列的过程中，若dp[j] + 1 > dp[i]时，以当前元素的为结尾的最长上升子序列的个数取决于j的最长上升子序列的个数；若dp[j] + 1 == dp[i]，在原来的基础上，加上j的个数。
class Solution {
public int findNumberOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int[] count = new int[nums.length];
dp[0] = 1;
count[0] = 1;
int max = 1;
int ans = 1;
for(int i = 1; i < nums.length; i++){
dp[i] = 1;
count[i] = 1;
for(int j = 0; j < i; j++){
if(nums[i] > nums[j]) {
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
count[i] = count[j];
} else if (dp[j] + 1 == dp[i]) {
count[i] += count[j];
}
}
}
if(dp[i] > max) {
max = dp[i];
ans = count[i];
}else if(dp[i] == max) {
ans += count[i];
}
}
return ans;
}
}
