N 次操作后的最大分数和

/*
思路：
1. 计算数组中所有可能的两两元素的最大公约数，并存储在一个表中。
2. 使用回溯法选择不同的元素对来计算得分，并记录最大得分。
3. 每次操作时，我们选择剩余元素中的最大公约数对，计算得分并删除这些元素。

Java Stream 版本：利用递归生成所有的子集组合，计算最大得分。
*/

import java.util.*;
import java.util.stream.IntStream;

public class MaxScoreStream {
    public int maxScore(int[] nums) {
        int n = nums.length / 2;
        return maxScore(nums, (1 << nums.length) - 1, new int[1 << nums.length]);
    }

    private int maxScore(int[] nums, int mask, int[] dp) {
        if (dp[mask] != 0) return dp[mask];
        int pairs = Integer.bitCount(mask) / 2;
        return dp[mask] = IntStream.range(0, nums.length).filter(i -> (mask & (1 << i)) != 0)
            .boxed().flatMap(i -> IntStream.range(i + 1, nums.length)
                .filter(j -> (mask & (1 << j)) != 0)
                .mapToObj(j -> new int[]{i, j}))
            .mapToInt(pair -> pairs * gcd(nums[pair[0]], nums[pair[1]]) + maxScore(nums, mask ^ (1 << pair[0]) ^ (1 << pair[1]), dp))
            .max().orElse(0);
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}