《寻找最大值》题目分析

如果我们用f[i][0/1]表示{Aj}中的最大值和次大值，其中Aj满足Aj & i = i

那么用如下代码可完成f数组的计算

for(int j = 19; j >= 0; j--) {
    for(int i = (1<<20) - 1; i >= 0; i--) {
        if(i & (1<<j)) {
            update(i - (1<<j), f[i][0]);
            update(i - (1<<j), f[i][1]);
        }
    }
}

其中f[i][0/1]的初始值是{Aj}中的最大值和次大值，其中Aj满足Aj = i

update(i, z) 表示用z更新f[i]

最终的答案ans = max(f[i][0] * f[i][1] * i)

上面这个计算技巧也被称为"n维前缀和"或者"高维前缀和"。大家可以参考 这里 和 这里 以及搜索相关资料了解详情。