Let dp[i][j] be the optimal answer to split nums[0..(i - 1)] into the first j andValues.
提示 2
dp[i][j] = min(dp[(i - z)][j - 1]) + nums[i - 1] over all x <= z <= y and dp[0][0] = 0, where x and y are the longest and shortest subarrays ending with nums[i - 1] and the bitwise-and of all the values in it is andValues[j - 1].
提示 3
The answer is dp[n][m].
提示 4
To calculate x and y, we can use binary search (or sliding window). Note that the more values we have, the smaller the AND value is.
提示 5
To calculate the result, we need to support RMQ (range minimum query). Segment tree is one way to do it in O(log(n)). But we can use Monotonic Queue since the ranges are indeed “sliding to right” which can be reduced to the classical minimum value in sliding window problem, for a O(n) solution.
