My Java solution, use DP


  • 0
    J
    class Solution {
        public int findNumberOfLIS(int[] nums) {
            if(nums == null || nums.length == 0)
                return 0;
            int n = nums.length;
            int[] longestLen = new int[n];
            int[] count = new int[n];
            longestLen[0] = 1;
            count[0] = 1;
            int max = 1;
            for(int i = 1; i < n; i++) {
                int j = 0;
                int m  = 0;
                int maxLen = 0;
                while(j < i) {
                    if(nums[i] > nums[j]) {
                      if(longestLen[j] > maxLen) {
                          maxLen = longestLen[j];
                          m = count[j];
                      }else if(longestLen[j] == maxLen) {
                          m += count[j];
                      }  
                    }
                    j++;
                }
                longestLen[i] = maxLen + 1;
                count[i] = m == 0 ? 1:m;
                max = Math.max(max, longestLen[i]);
                
            }
            int sum = 0;
            for(int i = 0; i < n; i++)
                if(max == longestLen[i])
                    sum += count[i];
            return sum;
            
        }
    }
    

Log in to reply
 

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