Share my 29ms space cost(n) & time cost(n^2) Java solution


  • 0
    S
    import java.util.*;
    
    public class Solution {
        //s:n + n + n -> O(n) 
        //t:nlogn + n + n^2 + n -> O(n^2)
        //d(i) = max(d(k) + 1), k < i && nums[i] % nums[k] == 0;
        public List<Integer> largestDivisibleSubset(int[] nums) {
            if(nums == null || nums.length == 0) {
                return new ArrayList<>();
            }
            Arrays.sort(nums); //t:nlogn
            int[] dp = new int[nums.length]; //s:n
            int[] prev = new int[nums.length];//s:n
            Arrays.fill(prev, -1);//t:n
    
            //t:n^2
            int index = 0, maxCount = 1;
            for (int i = 0; i < nums.length; ++i) { //t:n
                dp[i] = 1;
                for (int j = 0; j < i && nums[j] <= (nums[i] >>> 1); ++j) { //t:n/4
                    if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
                        dp[i] = dp[j] + 1;
                        prev[i] = j;
                    }
                    if (dp[i] > maxCount) {
                        maxCount = dp[i];
                        index = i;
                    }
                }
            }
            List<Integer> result = new LinkedList<>();//s:n
            //t:n
            for (; index != -1; index = prev[index]) {
                result.add(0, nums[index]);
            }
            return result;
        }
    }

Log in to reply
 

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