2680.最大或值

prefix sum, bit manipulation, greedy, https://leetcode.cn/problems/maximum-or/

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k 。每一次操作中，你可以选择一个数并将它乘 2 。

你最多可以进行 k 次操作，请你返回 nums[0] | nums[1] | ... | nums[n - 1] 的最大值。

a | b 表示两个整数 a 和 b 的 按位或 运算。

示例 1：

输入：nums = [12,9], k = 1
输出：30
解释：如果我们对下标为 1 的元素进行操作，新的数组为 [12,18] 。此时得到最优答案为 12 和 18 的按位或运算的结果，也就是 30 。

示例 2：

输入：nums = [8,1,2], k = 2
输出：35
解释：如果我们对下标 0 处的元素进行操作，得到新数组 [32,1,2] 。此时得到最优答案为 32|1|2 = 35 。

提示：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= 15

python

class Solution:
    def maximumOr(self, nums: List[int], k: int) -> int:
        highest = 0
        prefix_or = [0]
        suffix_or = [0] * (len(nums) + 1)
        
        # 计算前缀或
        for num in nums:
            prefix_or.append(prefix_or[-1] | num)
        
        # 计算后缀或
        for i in range(len(nums) - 1, -1, -1):
            suffix_or[i] = suffix_or[i + 1] | nums[i]
        
        # 遍历每个数，考虑对其执行k次操作后的效果
        for i in range(len(nums)):
            original = nums[i]
            shifted = original << k  # 对当前数进行k次乘2，等效于左移k位
            result = prefix_or[i] | shifted | suffix_or[i + 1]
            highest = max(highest, result)
        
        return highest

在代码中，prefix_or 和 suffix_or 数组分别存储了从数组开始到当前元素（不包括当前元素）的所有元素的按位或结果，以及从数组末尾到当前元素（不包括当前元素）的所有元素的按位或结果。因此：

prefix_or[i] 实际上包含了所有在索引 i 之前（不包括 i）的元素的按位或。
suffix_or[i + 1] 包含了所有在索引 i 之后（不包括 i）的元素的按位或。

例如：

prefix_or[1] 是 prefix_or[0] 与 nums[0] 的按位或结果，等同于仅包含 nums[0] 的按位或结果。

Q: "考虑到按位或运算的特性，提高某一位上的值可以增加整体的结果。由于可以对任意一个数字进行最多k次的翻倍（即左移操作），这意味着可以尝试将这k次机会用在一个能带来最大收益的数字上，而不是分散使用"，集中与分散使用是等价的？

实际上，集中使用 k 次乘 2（即左移操作）在一个数上并不与分散这些操作在多个数上等价。这里的关键在于按位或运算的性质以及最大化最终结果的目标。
集中 vs 分散
集中使用：将所有的 k 次机会都用在一个数上意味着你选择一个数并将其值尽可能地放大。这样做可以显著提高该数在高位上的贡献，从而可能大幅增加整个数组元素进行按位或运算后的结果。
分散使用：如果将这 k 次机会分散到多个不同的数上，虽然每个数都会有所增长，但这种增长对于整体按位或的结果来说可能不如集中于一个数有效。因为按位或运算关注的是每一位是否至少有一个1，分散应用可能会导致高位的提升不如集中在单个数上显著。
为什么集中更优？
按位或运算的一个重要特性是它是一个“无记忆”操作，这意味着一旦某一位上有1，无论后续添加多少个0或是1，这一位的结果都不会改变。因此，为了最大化按位或的结果，最理想的情况是在尽可能高的位上得到1。通过将所有 k 次操作集中应用于一个数，你可以确保这个数在其二进制表示的较高位置上有更多的1，这比在多个数的较低位置上产生1更加有效。
例如，考虑两个数字 a=8 (1000) 和 b=1 (0001)，如果你有2次乘2的机会：
如果你将这两次机会都用在 a 上 (a=32 (100000)), 最终的按位或可能是更大的，因为你提高了最高位的权重。
如果你分别给 a 和 b 各一次机会 (a=16 (10000), b=2 (00010)), 虽然两个数都有所增长，但是相比集中策略，其对整体按位或结果的提升效果较弱。
结论
因此，将 k 次机会集中在能够带来最大收益的单个数上通常是更有效的策略，而不是分散使用。这是因为这样做可以最大程度地利用高位的优势来增加最终按位或结果的价值。这种方法不是与分散使用等价，而是在大多数情况下更为优越。

2680.最大或值 ​

2680.最大或值