Q47 Number of Longest Increasing Subsequence - LeetCode 673

PHOTO EMBED

Sat Sep 09 2023 16:39:50 GMT+0000 (Coordinated Universal Time)

Saved by @Ayush_dabas07 

class Solution {
    public int findNumberOfLIS(int[] nums) {
        //find LIS  -> traverse the array and find dp[i] = max and count++
        int n = nums.length , max = 1 ;
        int dp[] = new int[n] , count[] = new int[n];
        Arrays.fill(dp , 1);
        Arrays.fill(count, 1);
        for(int i = 0 ;i < n ; i++){
            for(int j = i-1 ; j>=0 ;j--){

                if(nums[j] < nums[j]){
                    if(1 + dp[j] > dp[i]){
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    }
                    else if (1+ dp[j] == dp[i]){
                        count[i]+= count[j];
                    }
                }
            }

            max = Math.max(max , dp[i]);
        }

        int ans = 0;
        for(int i = 0 ;i < n ; i++){
            if(dp[i] == max)
            ans += count[i];
        }

        return ans;
    }
}
content_copyCOPY

https://leetcode.com/problems/number-of-longest-increasing-subsequence/