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) {
        if (nums.length == 0) {
            return 0;
        }
        Map<Integer, Integer> map = new HashMap<>();
        int max = 0;
        MaxCount[] memo = new MaxCount[nums.length];
        for (int i = 0; i < nums.length; i++) {
            MaxCount mc = longestIncreasingSubsequence(nums, i, memo);
            int longest = mc.max + 1;
            if (!map.containsKey(longest)) {
                map.put(longest, mc.count);
            } else {
                map.put(longest, map.get(longest) + mc.count);
            }
            max = Math.max(max, longest);
        }
        return map.getOrDefault(max, 1);
    }

    private static class MaxCount {
        private final int max;
        private final int count;

        public MaxCount(int max, int count) {
            this.max = max;
            this.count = count;
        }
    }

    private static MaxCount longestIncreasingSubsequence(int[] nums, int idx, MaxCount[] memo) {
        if (memo[idx] != null) {
            return memo[idx];
        }
        int max = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = idx; i < nums.length; i++) {
            if (nums[idx] < nums[i]) {
                MaxCount mc = longestIncreasingSubsequence(nums, i, memo);
                int longest = mc.max + 1;
                if (!map.containsKey(longest)) {
                    map.put(longest, mc.count);
                } else {
                    map.put(longest, map.get(longest) + mc.count);
                }
                max = Math.max(max, longest);
            }
        }
        MaxCount maxCount = new MaxCount(max, map.getOrDefault(max, 1));
        memo[idx] = maxCount;
        return maxCount;
    }
}

@@ -345,32 +345,55 @@
    int max = 0;%0A
+        int count = 1;%0A
         MaxCount
@@ -429,16 +429,16 @@
 ength%5D;%0A
-
         
@@ -606,33 +606,22 @@
 if (
-!
 ma
-p.containsKey(
+x %3C 
 longest)
 ) %7B%0A
@@ -608,33 +608,32 @@
  (max %3C longest)
-)
  %7B%0A             
@@ -635,32 +635,24 @@
         
-map.put(longest,
+count +=
  mc.coun
@@ -644,33 +644,32 @@
 ount += mc.count
-)
 ;%0A            %7D 
@@ -677,61 +677,54 @@
 lse 
-%7B%0A                map.put(longest, map.get(longest)
+if (max == longest) %7B%0A                count
  +
+=
  mc.
@@ -720,33 +720,32 @@
 ount += mc.count
-)
 ;%0A            %7D%0A
@@ -815,32 +815,13 @@
 urn 
-map.getOrDefault(max, 1)
+count
 ;%0A  
@@ -1252,51 +1252,21 @@
     
-Map%3CInteger, Integer%3E map = new HashMap%3C%3E()
+int count = 1
 ;%0A  
@@ -1493,33 +1493,22 @@
 if (
-!
 ma
-p.containsKey(
+x %3C 
 longest)
 ) %7B%0A
@@ -1503,17 +1503,16 @@
 longest)
-)
  %7B%0A     
@@ -1526,32 +1526,24 @@
         
-map.put(longest,
+count +=
  mc.coun
@@ -1535,33 +1535,32 @@
 ount += mc.count
-)
 ;%0A              
@@ -1567,16 +1567,36 @@
   %7D else
+ if (max == longest)
  %7B%0A     
@@ -1614,43 +1614,16 @@
     
-map.put(longest, map.get(longest)
+count
  +
+=
  mc.
@@ -1627,17 +1627,16 @@
 mc.count
-)
 ;%0A      
@@ -1767,32 +1767,13 @@
 ax, 
-map.getOrDefault(max, 1)
+count
 );%0A 

Update problem 673