Use TreeMap to memorize, O(n^2)


  • 0
    R

    Use TreeMap to memorize. Idea is to iterate previous done ones for the longest. O(n^2)

    public class Solution {
        public int[] largestDivisibleSubset(int[] nums) {
            Arrays.sort(nums);
            Map<Integer, int[]> done = new TreeMap<>(); // num to (len, previous)
            int max = 0;
            int maxNum = -1;
            for (int num: nums) {
                int len = 1;
                int prev = -1;
                for (int d: done.keySet()) {
                    if (num % d == 0) {
                        if (len < done.get(d)[0] + 1) {
                            len = done.get(d)[0] + 1;
                            prev = d;
                        }
                    }
                }
                if (len > max) {
                    max = len;
                    maxNum = num;
                }
                done.put(num, new int[]{len, prev});
            }
            int[] ret = new int[max];
            for (int i=max-1; i>=0; i--) {
                ret[i] = maxNum;
                maxNum = done.get(maxNum)[1];
            }
            return ret;
        }
    }

Log in to reply
 

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