Largest Divisible Subset LeetCode solution in Java

1
class Solution {
2
  public List<Integer> largestDivisibleSubset(int[] nums) {
3
    Arrays.sort(nums);
4
    int N = nums.length;
5
    List<Integer> ans = new ArrayList<Integer>();
6
    int[] dp = new int[N];
7
    Arrays.fill(dp, 1);
8
    int[] hash = new int[N];
9
    for (int i = 0; i < N; i++) {
10
      hash[i] = i;
11
    }
12
    int lastindex = 0;
13
    int maxi = 1;
14
    for (int i = 0; i < N; i++) {
15
      for (int j = 0; j < i; j++) {
16
        if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
17
          dp[i] = dp[j] + 1;
18
          hash[i] = j;
19
        }
20
        if (dp[i] > maxi) {
21
          maxi = dp[i];
22
          lastindex = i;
23
        }
24
      }
25
    } // for ends
26
    ans.add(nums[lastindex]);
27
    while (hash[lastindex] != lastindex) {
28
      lastindex = hash[lastindex];
29
      ans.add(nums[lastindex]);
30
    }
31
    return ans;
32
  }
33
}