0动态规划中等 LeetCode673. 最长递增子序列的个数

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

描述

给定一个未排序的整数数组 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;
    }
}