Java easy dp solution


  • 0
    H
    class Solution {
        public int findNumberOfLIS(int[] nums) {
            if(nums == null || nums.length == 0) return 0;
            
            int dp[] = new int[nums.length];
            int count[] = new int[nums.length];
            Arrays.fill(count,1);
            Arrays.fill(dp,1);
            int max = 1;
            for(int i = 0; i < nums.length; i++){
                for(int j = 0; j < i; j++){
                    if(nums[i] > nums[j]) {
                      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];
                      }
                    }
                }
                max = Math.max(max,dp[i]);
            }
            
            int res = 0;
            for(int i = 0; i < dp.length; i++){
                if(dp[i] == max) res += count[i];
            }
            
            return res;
        }
    }
    
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.