題目連結(jié)：
題目意譯：
你被給定一個索引值從 0 開始數(shù)且長度為 n 的整數(shù)陣列 nums 以及一整數(shù) k。在一次操作中，你可以選擇一個元素並將其值乘以 2。
回傳藉由最多 k 次操作可以得到的 nums[0] | nums[1] | ... | nums[n - 1] 之最大值。
注意到 a | b 代表著兩整數(shù) a 和 b 按位元 OR 之操作。
限制：
1 ≦ nums.length ≦ 10 ^ 5
1 ≦ nums[i] ≦ 10 ^ 9
1 ≦ k ≦ 15
範例測資：
範例 1：
輸入： nums = [12,9], k = 1
輸出： 30
解釋： 如果我們對索引值 1 執(zhí)行一次操作，我們新的陣列 nums 變?yōu)?[12,18]。因此，我們回傳 12 和 18 按位元 OR 之值，其為 30。
範例 2：
輸入： nums = [8,1,2], k = 2
輸出： 35
解釋： 如果我們對索引值 0 執(zhí)行兩次操作，我們新的陣列 nums 變?yōu)?[32,1,2]。因此，我們回傳 32|1|2 = 35。
解題思維：
首先，我們可以看到這 k 次操作在最佳解中應(yīng)當集中套用在同一個數(shù)字上。由於證明只是一個單純的反證法——即假設(shè)最佳解不是 k 次操作集中在同一個數(shù)字，然後你就會發(fā)現(xiàn)改成集中在同一個數(shù)字上會產(chǎn)出更大的結(jié)果。故而矛盾。細節(jié)就不贅述了。
那要選哪個數(shù)字呢？不知道。既然不知道那就全做，因此我們先計算出所有可能的前綴 OR 結(jié)果和後綴 OR 結(jié)果。然後再掃過每一個索引值 i，把 k 次操作都套用在 nums[i] 上試試看，而結(jié)果將會是
0 ~ i - 1 這個前綴的 OR 結(jié)果 | nums[i] × (2 ^ k) | i + 1 ~ nums.length - 1 這個後綴之 OR 結(jié)果
取所有索引值中的結(jié)果最大值即可。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
