Leetcode 673) Number of Longest Increasing Subsequence

11 Aug 2021 in Algorithms

내 답안

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


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

        for(int i=1;i<nums.length;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    if(1+dp[j] > dp[i]){
                        dp[i]=dp[j]+1;
                        cnt[i]=cnt[j];
                    }else if(1+dp[j]==dp[i]){
                        cnt[i]+=cnt[j];
                    }
                }                       
            }
        }
        int max = 0;
        for(int i: dp){
            max = Math.max(i,max);
        }

        int ans = 0;
        for(int i = 0; i < dp.length; ++i){
            if(dp[i] == max){
                ans += cnt[i];
            }
        }

        return ans;
    }
}

다른 답안

class Solution {
    public int findNumberOfLIS(int[] nums) 
    {
        int n = nums.length;
        int[] lis = new int[n];
        int[] count = new int[n];
        Arrays.fill(lis,1);
        Arrays.fill(count,1);
        for(int i=1; i<n; i++)
        {
            for(int j=0; j<i; j++)
            {
                if(nums[i] > nums[j])
                {
                    if(lis[j]+1 > lis[i])
                    {
                        lis[i] = lis[j]+1;
                        count[i] = count[j];
                    }
                    else if(lis[i] == lis[j] + 1)
                    {
                        count[i] = count[i] + count[j]; // [1,2,2,3] to handle this case
                    }
                }
               
            }
           
        }
 
        int maxLis = 0;
        
        for(int i=0; i<n; i++)
        {
            maxLis = Math.max(lis[i],maxLis);
        }

        int res = 0;
        
        for(int i=0; i<n; i++)
        {
            if(lis[i] == maxLis) res += count[i];
        }
        return res;
    }
}