Java DP solution with explanation


  • 0
    J
      public List<Integer> largestDivisibleSubset(int[] nums) {
        if (nums.length == 0) {
          return new ArrayList<Integer>();
        }
        int[] nextIdx = new int[nums.length];
        int[] maxLength = new int[nums.length];
        int max = 0, maxIdx = 0;
        Arrays.sort(nums);
        for (int i = nums.length - 1; i >= 0; i--) {
          maxLength[i] = 1;
          for (int j = nums.length - 1; j > i; j--) {
            if (nums[j] % nums[i] == 0) {
              if (maxLength[j] + 1 > maxLength[i]) {
                maxLength[i] = maxLength[j] + 1;
                nextIdx[i] = j;
                if (maxLength[i] > max) {
                  maxIdx = i;
                }
              }
            }
          }
        }
        List<Integer> res = new ArrayList<Integer>();
        res.add(nums[maxIdx]);
        int idx = nextIdx[maxIdx];
        while (idx != 0) {
          res.add(nums[idx]);
          idx = nextIdx[idx];
        }
        return res;
      }
    

    The idea is to keep track of the next element in the array that gives the longest streak for each element in the array, then in the end, we find the start of the maximal streak, then start from there and find the rest of elements.

    nextIdx is an array keeping track of the next element indexed j for each element at i that gives the longest streak, and maxLength keeps track of the current max length for each element. The core algorithm is: for each element at i, we go from n-1 to i+1 to find the best j, and we link i to j by specifying that nextIdx[i] = j.

    After we have iterated every element, we start from the maxIdx, which points to the first element in the longest streak. We add that element to our result, then go to the next element according to nextIdx until we reach the last element in that streak, who will have value 0 in its nextIdx slot.

    Hope this helps.


Log in to reply
 

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