【LeetCode】3670. 没有公共位的整数最大乘积 (SOSDP)

3670. 没有公共位的整数最大乘积 - 力扣（LeetCode）

题目：

思路：

SOSDP

本题我们显然不能枚举每一个数对，n² 的复杂度显然超时，所以考虑优化

我们考虑一个二进制数 mask，因为我们必须要选没有任何公共位置的数才行，那么我们参考集合论，其实就是去找 ~mask 的子集中的最大值

那么显然问题变为如何找子集的最大值，我们可以考虑动态规划的思想，假设如果我们要找 mask 的子集最大值，那么是不是可以找 mask 所有子集的子集的最大值，以此类推，我们可以一步一步求出所有子集的最大值

具体的，我们定义 f[i] 为 i 的子集中的最大值，初始化 f[x] = x（如果含有 x），然后套板子即可

其实这就是板子的变形，从求前缀和变成了前缀最大值，具体实现看代码

前缀和情况如下

//从地位向高位枚举
for (int i = 0; i < k; i++) {//枚举状态for (int mask = 0; mask < (1 << k); mask++) {//判断这一位有没有，即是不是子集if (mask >> i & 1) f[mask] += f[mask ^ (1 << i)];}
}

代码：

class Solution {
public:long long maxProduct(vector<int>& nums) {int mx = 0;for (auto& x : nums)mx = max(mx, x);int m = __lg(mx) + 1;mx = 1 << m;vector<int> f(mx,0);for (auto & x : nums)f[x] = x;for (int i = 0; i < m; i++) {for (int j = 0; j < mx; j++) {if (j >> i & 1) {f[j] = max(f[j], f[j ^ (1 << i)]);}}}long long ans = 0;for (auto& x : nums) {int buji = (mx - 1) ^ x;ans = max(ans, 1LL * x * f[buji]);}return ans;}
};