0673 - Number of Longest Increasing Subsequence

0673 - Number of Longest Increasing Subsequence

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

Examples

Input: nums = [1,3,5,4,7] Output: 2 Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].

Input: nums = [2,2,2,2,2] Output: 5 Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

Constraints

• 1 <= nums.length <= 2000

• -106 <= nums[i] <= 106

Java Solution (Dynammic Programming)

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        
        int[]dp = new int[n];
        Arrays.fill(dp,1);
        
        int[]end = new int[n];
        Arrays.fill(end,1);

        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                
                if(nums[j]<nums[i]){
            
                    if(dp[j]+1==dp[i])end[i]+=end[j];
                    if(dp[j]+1>dp[i])end[i]=end[j];
                    
                    dp[i]=Math.max(dp[j]+1,dp[i]);
                }
            }
        }
        
        int max = 0;
        for(int num:dp) max = Math.max(max,num);
        
        int res = 0;
        for(int i=0;i<n;i++){
            if(dp[i]==max)res+=end[i];
        }
        return res;
    }
}