package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/number-of-longest-increasing-subsequence/
 */
public class Problem673 {
    public int findNumberOfLIS(int[] nums) {
        Integer[] memo = new Integer[nums.length];
        Map<Integer, Integer> map = new HashMap<>();
        int max = longestIncreasingSubsequence(nums, 0, memo, map);
        return map.get(max);
    }

    private static int longestIncreasingSubsequence(int[] nums, int idx, Integer[] memo,
                                                    Map<Integer, Integer> map) {
        if (idx == nums.length) {
            return 0;
        }
//        if (memo[idx] != null) {
//            int max = memo[idx];
//            if (!map.containsKey(max)) {
//                map.put(max, 1);
//            } else {
//                map.put(max, map.get(max) + 1);
//            }
//            System.out.println("max: " + max);
//            return max;
//        }
        int max = 0;
        for (int i = idx + 1; i < nums.length; i++) {
            if (nums[idx] < nums[i]) {
                max = Math.max(max, longestIncreasingSubsequence(nums, i, memo, map) + 1);
            }
            max = Math.max(max, longestIncreasingSubsequence(nums, i, memo, map));
        }
        memo[idx] = max;
        if (!map.containsKey(max)) {
            map.put(max, 1);
        } else {
            map.put(max, map.get(max) + 1);
        }
//        System.out.println("max: " + max);
        return max;
    }

    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
        System.out.println(prob.findNumberOfLIS(new int[]{1, 2, 3, 4, 5})); // 1
        System.out.println(prob.findNumberOfLIS(new int[]{1, 3, 3, 4, 5})); // 2
    }
}

@@ -219,59 +219,8 @@
 ) %7B%0A
-        Integer%5B%5D memo = new Integer%5Bnums.length%5D;%0A
     
@@ -290,116 +290,135 @@
 x = 
-longestIncreasingSubsequence(nums, 0, memo, map);%0A        return map.get(max);%0A
+0;%0A        Integer%5B%5D memo = new Integer%5Bnums.length%5D;%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A 
     
-%7D%0A%0A
+   
     
-private static int
+int longest =
  lon
@@ -447,264 +447,70 @@
 nce(
-int%5B%5D 
 nums, i
-nt 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//
+, memo) + 1;%0A            max = Math.max(max, longest);%0A
     
@@ -542,18 +542,20 @@
 Key(
-max
+longest
 )) %7B%0A
-//
     
@@ -578,19 +578,21 @@
 put(
-max
+longest
 , 1);%0A
-//
     
@@ -608,18 +608,16 @@
  else %7B%0A
-//
         
@@ -624,35 +624,39 @@
         map.put(
-max
+longest
 , map.get(max) +
@@ -649,27 +649,31 @@
 map.get(
-max
+longest
 ) + 1);%0A
 //      
@@ -664,18 +664,16 @@
 ) + 1);%0A
-//
         
@@ -682,59 +682,178 @@
   %7D%0A
-//
+   
      
+%7D%0A
        
-System.out.println(%22max: %22 + max);%0A//
+ return map.get(max);%0A    %7D%0A%0A    private static int longestIncreasingSubsequence(int%5B%5D nums, int idx, Integer%5B%5D memo) %7B%0A        if (memo%5Bidx%5D != null) %7B%0A
     
@@ -872,14 +872,18 @@
 rn m
-ax;%0A//
+emo%5Bidx%5D;%0A
     
@@ -933,20 +933,16 @@
  i = idx
- + 1
 ; i %3C nu
@@ -1076,21 +1076,16 @@
  i, memo
-, map
 ) + 1);%0A
@@ -1110,112 +1110,49 @@
     
+%7D%0A
     
-max = Math.max(max, longestIncreasingSubsequence(nums, i, memo, map));%0A        %7D%0A        memo%5Bidx%5D =
+    memo%5Bidx%5D = max;%0A        return
  max
@@ -1161,78 +1161,110 @@
     
+%7D%0A%0A
     
-if (!map.containsKey(max)) %7B%0A            map.put(max, 1
+public static void main(String%5B%5D args) %7B%0A        Problem673 prob = new Problem673(
 );%0A
+//
         
 %7D el
@@ -1263,234 +1263,152 @@
     
-%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%0A    public static void main(String%5B%5D args) %7B%0A        Problem673 prob = new Problem673();%0A
+System.out.println(prob.findNumberOfLIS(new int%5B%5D%7B1, 2%7D)); // 1%0A//        System.out.println(prob.findNumberOfLIS(new int%5B%5D%7B3, 5, 2, 4%7D)); 
 //
+ 2%0A
     
@@ -1567,16 +1567,18 @@
 ); // 5%0A
+//
         
@@ -1650,16 +1650,18 @@
 ); // 1%0A
+//
         

Update problem 673