最长递增子序列的个数

最长递增子序列的个数

public class Solution {  
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] count = new int[n];

        Arrays.fill(dp, 1);
        Arrays.fill(count, 1);

        int maxLength = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                //没递增，直接下一个
                if (nums[i] <= nums[j]) {
                    continue;
                }
                //是递增
                if (dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    //记录数量
                    count[i] = count[j];
                } else if (dp[i] == dp[j] + 1) {
                    //两个相同长度的结果，累加
                    count[i] += count[j];
                }
            } 
            //最长序列数
            maxLength = Math.max(maxLength, dp[i]);
        }
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == maxLength) {
                result += count[i];
            }
        }
        return result;
    }
}