package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * https://leetcode.com/problems/largest-divisible-subset/
 */
public class Problem368 {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            List<Integer> tmp = largestDivisibleSubset(nums, i, 1, new HashMap<>());
            if (result.size() < tmp.size()) {
                result = tmp;
            }
        }
        return result;
    }

    private List<Integer> largestDivisibleSubset(int[] nums, int cur, int prev,
                                                 Map<String, List<Integer>> memo) {
        if (cur == nums.length) {
            return new ArrayList<>();
        }
        String key = cur + "|" + prev;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        int newPrev = prev;
        boolean found = false;
        if (prev > 0) {
            if (nums[cur] % prev == 0) {
                found = true;
                newPrev = nums[cur];
            }
        }
        List<Integer> result = largestDivisibleSubset(nums, cur + 1, newPrev, memo);
        if (found) {
            result.add(nums[cur]);
        }
        memo.put(key, result);
        return result;
    }

    public static void main(String[] args) {
        Problem368 prob = new Problem368();
//        System.out.println(prob.largestDivisibleSubset(new int[]{546, 669})); // [546]
//        System.out.println(prob.largestDivisibleSubset(new int[]{1, 2, 3})); // [1, 2]
//        System.out.println(prob.largestDivisibleSubset(new int[]{1, 2, 3, 6})); // [1, 2, 6]
//        System.out.println(prob.largestDivisibleSubset(new int[]{1, 2, 4, 8})); // [1, 2, 4, 8]
//        System.out.println(prob.largestDivisibleSubset(new int[]{1, 2, 4, 8, 9, 72})); // [1, 2, 4, 8, 72]
//        System.out.println(prob.largestDivisibleSubset(new int[]{1, 2, 3, 4, 6, 24})); // [1, 2, 4, 24]
//        System.out.println(prob.largestDivisibleSubset(new int[]{3, 4, 16, 8})); // [4, 8, 16]
        System.out.println(prob.largestDivisibleSubset(new int[]{1, 3, 9, 18, 54, 90, 108, 180, 720, 972})); // [1, 3, 9, 18, 90, 180, 360, 720]
    }
}

@@ -1010,28 +1010,133 @@
     
-int newPrev = prev;%0A
+List%3CInteger%3E largest = new ArrayList%3C%3E();%0A        int newPrev = prev;%0A        for (int i = cur; i %3C nums.length; i++) %7B%0A    
     
@@ -1166,24 +1166,28 @@
 se;%0A        
+    
 if (prev %3E 0
@@ -1198,24 +1198,28 @@
             
+  
+  
 if (nums%5Bcur
@@ -1215,19 +1215,17 @@
 f (nums%5B
-cur
+i
 %5D %25 prev
@@ -1249,16 +1249,20 @@
         
+    
 found = 
@@ -1283,16 +1283,20 @@
         
+ 
+   
 newPrev 
@@ -1306,14 +1306,16 @@
 ums%5B
-cur%5D;%0A
+i%5D;%0A    
     
@@ -1324,34 +1324,42 @@
       %7D%0A        
-%7D%0A
+    %7D%0A    
         List%3CInt
@@ -1402,19 +1402,17 @@
 t(nums, 
-cur
+i
  + 1, ne
@@ -1425,16 +1425,83 @@
  memo);%0A
+            List%3CInteger%3E newResult = new ArrayList%3C%3E(result);%0A    
         
@@ -1521,25 +1521,32 @@
             
-r
+    newR
 esult.add(nu
@@ -1552,15 +1552,131 @@
 ums%5B
-cur
+i
 %5D);%0A
+            %7D%0A            if (largest.size() %3C newResult.size()) %7B%0A                largest = newResult;%0A            %7D%0A
     
@@ -1703,21 +1703,22 @@
 ut(key, 
-resul
+larges
 t);%0A    
@@ -1720,37 +1720,38 @@
 %0A        return 
-resul
+larges
 t;%0A    %7D%0A%0A    pu
@@ -2611,16 +2611,21 @@
 08, 180,
+ 360,
  720, 97

Update problem 368