Maximize Score After N Operations LeetCode solution in Java

1
class Solution {
2
  public int maxScore(int[] nums) {
3
    int n = nums.length;
4
    Map<Integer, Integer> gcdVal = new HashMap<>();
5
    for (int i = 0; i < n; ++i) {
6
      for (int j = i + 1; j < n; ++j) {
7
        gcdVal.put((1 << i) + (1 << j), gcd(nums[i], nums[j]));
8
      }
9
    }
10

11
    int[] dp = new int[1 << n];
12

13
    for (int i = 0; i < (1 << n); ++i) {
14
      int bits = Integer.bitCount(i); // how many numbers are used
15
      if (bits % 2 != 0) // odd numbers, skip it
16
      continue;
17
      for (int k : gcdVal.keySet()) {
18
        if ((k & i) != 0) // overlapping used numbers
19
        continue;
20
        dp[i ^ k] = Math.max(dp[i ^ k], dp[i] + gcdVal.get(k) * (bits / 2 + 1));
21
      }
22
    }
23

24
    return dp[(1 << n) - 1];
25
  }
26

27
  public int gcd(int a, int b) {
28
    if (b == 0) return a;
29
    return gcd(b, a % b);
30
  }
31
}
32

33
// Time: O(2^n * n^2)
34
// Space: O(2 ^ n)