package leetcode;

/**
 * https://leetcode.com/problems/number-of-longest-increasing-subsequence/
 */
public class Problem673 {
    public int findNumberOfLIS(int[] nums) {
        // TODO
        return 0;
    }

    public static void main(String[] args) {
        Problem673 prob = new Problem673();
        System.out.println(prob.findNumberOfLIS(new int[]{1, 3, 5, 4, 7})); // 2
        System.out.println(prob.findNumberOfLIS(new int[]{2, 2, 2, 2, 2})); // 5
    }
}

@@ -12,16 +12,65 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -227,32 +227,1305 @@
     
-// TODO%0A        return 0
+Integer%5B%5D memo = new Integer%5Bnums.length%5D;%0A        Map%3CInteger, Integer%3E map = new HashMap%3C%3E();%0A        int max = longestIncreasingSubsequence(nums, 0, memo, map);%0A        return map.get(max);%0A    %7D%0A%0A    private static int longestIncreasingSubsequence(int%5B%5D nums, int idx, Integer%5B%5D memo,%0A                                                    Map%3CInteger, Integer%3E map) %7B%0A        if (idx == nums.length) %7B%0A            return 0;%0A        %7D%0A//        if (memo%5Bidx%5D != null) %7B%0A//            int max = memo%5Bidx%5D;%0A//            if (!map.containsKey(max)) %7B%0A//                map.put(max, 1);%0A//            %7D else %7B%0A//                map.put(max, map.get(max) + 1);%0A//            %7D%0A//            System.out.println(%22max: %22 + max);%0A//            return max;%0A//        %7D%0A        int max = 0;%0A        for (int i = idx + 1; i %3C nums.length; i++) %7B%0A            if (nums%5Bidx%5D %3C nums%5Bi%5D) %7B%0A                max = Math.max(max, longestIncreasingSubsequence(nums, i, memo, map) + 1);%0A            %7D%0A            max = Math.max(max, longestIncreasingSubsequence(nums, i, memo, map));%0A        %7D%0A        memo%5Bidx%5D = max;%0A        if (!map.containsKey(max)) %7B%0A            map.put(max, 1);%0A        %7D else %7B%0A            map.put(max, map.get(max) + 1);%0A        %7D%0A//        System.out.println(%22max: %22 + max);%0A        return max
 ;%0A  
@@ -1614,24 +1614,26 @@
 oblem673();%0A
+//
         Syst
@@ -1782,16 +1782,182 @@
 ); // 5%0A
+//        System.out.println(prob.findNumberOfLIS(new int%5B%5D%7B1, 2, 3, 4, 5%7D)); // 1%0A//        System.out.println(prob.findNumberOfLIS(new int%5B%5D%7B1, 3, 3, 4, 5%7D)); // 1%0A
     %7D%0A%7D%0A

Update problem 673