[LeetCode] 368. Largest Divisible Subset

 Problem : https://leetcode.com/problems/largest-divisible-subset/

For a valid subset in ascending order [A, B, C, D], if the largest number D can be divided by the Number e, then the subset [A, B, C, D, e] is still a valid subset.

Time Complexity = O ( N ** 2)

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
      int N = nums.length;

      // Maximum length of valid subset ends by the ith number,
      int[] count = new int[N];
      // Index of previous number, to which the ith number can be appended, to form the longest subset.
      int[] pre = new int[N];
      

      int maxSoFar = 0;
      int index = 0;

      Arrays.sort(nums);
      
      for (int i = 0; i < N; i++) {
        pre[i] = -1;
        count[i] = 1;
        for (int j = i - 1; j >= 0; j--) {
          if (nums[i] % nums[j] == 0) {
            // If nums[i] can be divided by nums[j], we can expend the subset ends by nums[j]
            // Because all nums[j] can be divided by all other numbers in the subset,
            // nums[i] can also be divided by other numbers in the current subset.
      
            // No need to update count[i], if nums[i] can form a longer subset with other number.
            if (count[j] + 1 > count[i]) {
              count[i] = count[j] + 1;
              pre[i] = j;
            
              if (maxSoFar < count[i]) {
                index = i;
                maxSoFar = count[i];
              }
            }
          }
        }
      }

      // Start from the last number of the longest subset and
      // iterate back to the beginner ( pre[index] == -1)
      LinkedList<Integer> result = new LinkedList<>();
      while (index != -1) {
        result.offerFirst(nums[index]);
        index = pre[index];
      }

      return result;
    }
}
        

Edited on: 04/06/2025. Add detail explanation to the steps.