假设有一个(m x n)位的二维数组。
例如：
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
0 0 0 0 1
在这里，m = 4，n = 5。
我可以翻转(0变成1，1变成0(任何一行中的位。当您翻转特定行中的位时，您将翻转所有位。
我的目标是获取给定行对之间的最大OR值。
也就是说，如果给定的一对行是(r1, r2)，那么我可以在r1和r2之间翻转任意数量的行，并且我应该找到r1和r2之间所有行的最大可能OR值。
在上面的例子中(考虑具有从 1 开始索引的数组(，如果r1= 1 并且r2= 4，我可以翻转第一行以获得0 1 1 0 1。现在，如果我找到从 1 到 4 的所有行的OR值，我会得到值31作为最大可能的OR值(可能还有其他解决方案(。
此外，最好计算(r1, r1)、(r1, r1+1)、(r1, r1+2)、...、(r1, r2-1)的答案，同时计算相同的(r1,r2)。
约束
1 <= m x n <= 10^6
1 <= r1 <= r2 <= m
一个简单的蛮力解决方案的时间复杂度为O(2^m). 有没有更快的方法来计算这个？
自A <= A | B年以来，数字A的值只会随着我们向AOR更多的数字而上升。
因此，我们可以使用二叉搜索。
我们可以使用一个函数来获取两行之间的最大值，并将OR的结果保存为第三行。然后比较其中两行的第三行以获得更高级别的行，然后比较其中两个更高级别的行，依此类推，直到只剩下一个。
使用您的示例：
array1 = 1 0 0 1 0 [0]
1 0 1 0 0 [1]
1 0 1 1 0 [2]
0 0 0 0 1 [3]
array2 = 1 1 0 1 1 <-- [0] | ~[1]
1 1 1 1 0 <-- [2] | ~[3]
array3 = 1 1 1 1 1 <-- [0] | [1]
显然，当m不是 2 的幂时，您可以根据需要截断分支。
所以这将是O(m)时间。请记住，对于大量行，可能没有唯一的解决方案。结果很可能是2 ^ n - 1.
一个重要的优化：如果m >= n，则输出必须2 ^ n - 1。假设我们有两个数字 A 和 B。如果 B 有k数字缺失位，则保证A或~A至少填充其中一个位。出于类似的原因，如果m >= log n，则输出也必须2 ^ n - 1，因为每个A或~A保证至少填充一半未填充位的B。
使用这些快捷方式，您可以根据需要进行暴力搜索。我不是 100% 的二叉搜索算法在每种情况下都有效。
考虑到翻转整个矩阵中的行然后将它们组合在一起以获得尽可能多的 1 的问题，我声称当列数小于 2^m 时这是可以处理的，其中 m 是行数。逐个考虑这些行。在阶段 i 从 0 开始计数，您需要填充的零少于 2^(m-i(。因为翻转一行会将 0 变成 1，反之亦然，因此当前行或翻转的行将至少填充这些零的一半。当您完成所有行后，您将有少于 1 个零要填充，因此此过程保证提供完美的答案。
我声称当列数至少为 2^m 时，这是可以处理的，其中 m 是行数。翻转行有 2^m 种可能的模式，但这只是 O(N(，其中 N 是列数。因此，在这种情况下，尝试所有可能的翻转行模式会给你一个 O(N^2( 算法。