将数组划分为k个连续的子数组，以使每个子数组之和的按位与最大 [英] partition of array into k contiguous subarrays such that bitwise AND of sum of each subarray is maximum
问题描述
给出大小为 n （n <= 50）的包含正整数的数组。
必须将数组划分为 k 个连续的子数组，以使得所有的按位 AND
An array of size n (n<=50) containing positive integers is given.
You have to divide the array into k contiguous subarrays in such a way that the bitwise AND of all subarray sums is maximized.
例如，使用 array = [30,15,26,16,21] 和 k = 3 ，请考虑所有分区：
For example with array=[30,15,26,16,21] and k=3, consider all partitions:
- （30）& （15）& （26 + 16 + 21）= 14
- （30）& （15 + 26）& （16 + 21）= 0
- （30）& （15 + 26 + 16）& （21）= 16
- （30 + 15）& （26 + 16）& （21）= 0
- （30 + 15）& （26）& （16 + 21）= 0
- （30 + 15 + 26）& （16）& （21）= 0
- (30) & (15) & (26+16+21) = 14
- (30) & (15+26) & (16+21) = 0
- (30) & (15+26+16) & (21) = 16
- (30+15) & (26+16) & (21) = 0
- (30+15) & (26) & (16+21) = 0
- (30+15+26) & (16) & (21) = 0
最大为16，因此该数组的答案为16。
Maximum of all is 16, so the answer for this array is 16.
除了蛮力之外，我没有其他想法。
I am not getting any idea other than brute force. Please help.
static void findMaxAND(int[] arr,int k){
if (k>arr.length){
System.out.println(0);
return;
}
int n=arr.length;
int[] parSum=new int[n];
parSum[0]=arr[0];
for (int i=1;i<n;i++){
parSum[i]+=parSum[i-1]+arr[i];
}
int upperSum=parSum[n-1]/k;
int upperBit=(int)Math.floor((Math.log10(upperSum)/Math.log10(2)));
partitions=new ArrayList<>();
while (true){
int min=(int)Math.pow(2,upperBit);
check(arr,min,-1,new ArrayList<>(),1,k);
if (!partitions.isEmpty()){
int maxAND=Integer.MIN_VALUE;
for (List<Integer> partiton:partitions){
partiton.add(n-1);
int innerAND=parSum[partiton.get(0)];
for (int i=1;i<partiton.size();i++){
innerAND&=(parSum[partiton.get(i)]-parSum[partiton.get(i-1)]);
}
maxAND=Math.max(maxAND,innerAND);
}
System.out.println(maxAND);
break;
}
upperBit--;
}
}
private static List<List<Integer>> partitions;
static void check(int[] arr,int min,int lastIdx,List<Integer> idxs,int currPar,int k){
int sum=0;
if (currPar==k){
if (lastIdx>=arr.length-1){
return;
}
int i=lastIdx+1;
while (i<arr.length){
sum+=arr[i];
i++;
}
if ((sum&min)!=0){
partitions.add(new ArrayList<>(idxs));
}
}
if (currPar>k||lastIdx>=(arr.length-1)){
return;
}
sum=0;
for (int i=lastIdx+1;i<arr.length;i++){
sum+=arr[i];
if ((sum&min)!=0){
idxs.add(i);
check(arr,min,i,idxs,currPar+1,k);
idxs.remove(idxs.size()-1);
}
}
}
它可以工作，但是时间复杂太糟糕了。
It is working but time complexity is too bad.
推荐答案
下面是一种非递归动态编程解决方案（在JavaScript中，尽管它应该非常容易将其移植到Java）。它的工作方式与user3386109的注释和גלעדברקן的答案所建议的类似，尽管我不确定是否完全相同。 （它比我测试时גלעדברקן的回答要好得多，但这可能是由于实现上的细微差别，而不是有意义的概念上的差别。）
Below is a non-recursive dynamic-programming solution (in JavaScript, though it should be very straightforward to port it to Java). It works in a similar way to what user3386109's comment and גלעד ברקן's answer suggest, though I'm not sure if it's exactly the same. (It performed much better than גלעד ברקן's answer when I tested it, but that might be due to minor implementation differences rather than meaningful conceptual differences.)
总体复杂度最差-case O （ n 2 kb ）时间和 O （ nk ）额外的空间，其中<em> b 是要尝试的位数—我只是将其硬编码为下面的31，尽管在需要时可以通过排除较大的数字来对其进行优化，但是在实际中效果还不错。 （注意，我在这里假设加法和按位与是 O （1）。如果必须支持 really 大数，则实际的最坏情况下的时间复杂度将是 O （ n 2 kb 2 ）。）
Its overall complexity is worst-case O(n2kb) time and O(nk) extra space, where b is the number of bits to try — I just hardcoded it to 31 below, which performed just fine in practice, though you can optimize it if desired by ruling out larger numbers. (N.B. I'm assuming here that additions and bitwise-ANDs are O(1). If we have to support really large numbers, then the actual worst-case time complexity will be O(n2kb2).)
有关详细信息，请参见代码注释。
See code comments for details.
function f(array, numSegments) {
const n = array.length;
const maxBit = (1 << 30); // note: can improve if desired
if (numSegments > n) {
throw 'Too many segments.';
}
/* prefixSums[i] will be the sum of array[0..(i-1)], so that
* the sum of array[i..j] will be prefixSums[j+1]-prefixSums[i].
* This is a small optimization and code simplification, but the
* same asymptotic complexity is possible without it.
*/
const prefixSums = [];
prefixSums[0] = 0;
for (let i = 1; i <= n; ++i) {
prefixSums.push(prefixSums[i-1] + array[i-1]);
}
/* bestKnownBitmask will be the result -- the best bitmask that we
* could achieve. It will grow by one bit at a time; for example,
* if the correct answer is binary 1011, then bestKnownBitmask will
* start out as 0000, then later become 1000, then later 1010, and
* finally 1011.
*/
let bestKnownBitmask = 0;
/* startIndices[seg] will be a list of start-indices where
* it's possible to divide the range from such a start-index to
* the end of the array into 'seg' segments whose sums all satisfy
* a given bitmask condition.
*
* In particular, startIndices[0] will always be [n], because the
* only way to get zero segments is to have zero elements left; and
* startIndices[numSegments][0] will always be 0, because we only
* keep a bitmask condition if we successfully found a way to
* partition the entire array (0..(n-1)) into 'numSegments' segments
* whose sums all satisfied it.
*/
let startIndices = [];
startIndices.push([n]);
for (let seg = 1; seg <= numSegments; ++seg) {
startIndices.push([]);
for (let i = numSegments - seg; i <= n - seg; ++i) {
startIndices[seg].push(i);
}
}
for (let currBit = maxBit; currBit > 0; currBit >>= 1) {
const bitmaskToTry = (bestKnownBitmask | currBit);
const tmpStartIndices = startIndices.map(row => []); // empty copy
tmpStartIndices[0].push(n);
for (let seg = 1; seg <= numSegments; ++seg) {
for (const startIndex of startIndices[seg]) {
for (const nextIndex of tmpStartIndices[seg-1]) {
if (nextIndex <= startIndex) {
continue;
}
const segmentSum = prefixSums[nextIndex] - prefixSums[startIndex];
if ((segmentSum & bitmaskToTry) === bitmaskToTry) {
tmpStartIndices[seg].push(startIndex);
break;
}
}
}
}
if (tmpStartIndices[numSegments].length > 0
&& tmpStartIndices[numSegments][0] === 0) {
// success!
bestKnownBitmask = bitmaskToTry;
startIndices = tmpStartIndices;
}
}
return bestKnownBitmask;
}
function runFunctionAndLogResult(array, numSegments) {
let startTime = performance.now();
let result = f(array, numSegments);
let endTime = performance.now();
console.log(
'array = [' + array.join(', ') + ']\n' +
'k = ' + numSegments + '\n' +
'result = ' + result + '\n' +
'time = ' + (endTime - startTime) + ' ms'
);
}
runFunctionAndLogResult(
[ 25, 40, 45, 69, 26, 13, 49, 49, 84, 67, 30, 22, 43, 82, 2, 95, 96, 63, 78, 26, 95, 57, 80, 8, 85, 23, 64, 85, 12, 66, 74, 69, 9, 35, 69, 89, 34, 2, 60, 91, 79, 99, 64, 57, 52, 56, 89, 20, 8, 85 ],
12
);
这篇关于将数组划分为k个连续的子数组，以使每个子数组之和的按位与最大的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
