Java DP Solution. Is there anything I can do to improve the performance?


  • 0
    L

    My algorithm is:

    1. Sort the int array to ascending order.
    2. Iterate from first to last to compute every element's largest set.
    3. For each element, iterate the previous result to find the largest set with its last and largest element that can divide current element.

    The runtime of my program is 113ms. I wonder if I can improve the performance by some means. Thank you for your precious advices.

    public class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        if (nums == null || nums.length < 1) {
            return new ArrayList<Integer>();
        }
        
        List<List<Integer>> maxList = new ArrayList<List<Integer>>();
        List<Integer> currentList = null;
        List<Integer> best = null;
        List<Integer> result = new ArrayList<Integer>();
        
        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length; i++) {
            currentList = new ArrayList<Integer>();
            best = currentList;
            for (List<Integer> list : maxList) {
                if (((nums[i] % list.get(list.size() - 1)) == 0) 
                     && (list.size() > best.size())) {
                    best = list;
                } 
            }
            currentList.addAll(best);
            currentList.add(nums[i]);
            maxList.add(currentList);
            if (currentList.size() > result.size()) {
                result = currentList;
            }
        }
        
        return result;
    }
    

    }


  • 0

    Check my solution using DFS


Log in to reply
 

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