3670. 沒有公共位的整數最大乘積 - 力扣（LeetCode）

題目：

思路：

SOSDP

本題我們顯然不能枚舉每一個數對，n2 的復雜度顯然超時，所以考慮優化

我們考慮一個二進制數 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;}
};