将数组划分为k个连续子数组，使得每个子数组的和的按位与值最大。

Question

给出一个包含正整数的大小为 n（n≤50）的数组。你需要将数组分成 k 个连续子数组，使得所有子数组和的按位 AND 值最大。

例如，对于数组 [30,15,26,16,21] 和 k=3，考虑所有划分：

- (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。

我无法想到比暴力更好的方法，请帮忙。

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);
            }
        }
    }

它是工作的，但时间复杂度太差。

- vijay

---

我会集中精力一个部分接着一个部分来处理。数组的总和为108。因此，如果给定k=3，则最大可能的答案为36。所以，从值为32的位开始，看看能否将数组划分为具有位32设置的总和。如果不行，尝试将其划分为所有具有位16设置的总和。依此类推。 - user3386109

我认为这会起作用。你能给予更进一步的解释吗？谢谢。 - vijay

如果您发布生成暴力解决方案分区的代码，将会很有帮助。我的建议只是在此基础上进行优化。请注意，我假设您没有使用生成所有分区的库调用。 - user3386109

@user3386109，我已经添加了代码。 - vijay

在check方法中，当((sum & min) != 0)时，子数组是有效的。 - user3386109

Answer 1

以下是一个非递归的动态规划解决方案（使用JavaScript编写，但很容易移植到Java）。它的工作方式类似于用户3386109的评论和גלעד ברקן的答案建议的方式，尽管我不确定它是否完全相同。（当我测试时，它比גלעד ברקן的答案表现更好，但这可能是由于实现差异而不是有意义的概念差异。）

它的总体复杂度是最坏情况下O(n^2kb)时间和O(nk)额外空间，其中b是要尝试的位数 - 我在下面硬编码了31，这在实践中表现得很好，但如果需要可以通过排除更大的数字来进行优化。（请注意，我在这里假设加法和按位AND是O(1)。如果我们必须支持真正的大数字，则实际最坏情况时间复杂度将为O(n^2kb^2)。）

有关详细信息，请参见代码注释。

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
);

- ruakh

---

我已将您在我的答案下评论中提供的示例添加到我的代码片段运行的示例列表中。它似乎立即起作用了。为了说明您的代码执行“更好”，请提供某种可重复的参考。 - גלעד ברקן

@גלעדברקן：我以前从未尝试过这个“代码片段”功能，但好吧，我刚刚试了一下。这是你想要的吗？（有趣的是，它运行得比我之前运行的方式慢得多。我不确定这是否是“代码片段”功能的开销，还是其他原因。） - ruakh

很酷。我在你的代码上得到了大约12-16毫秒，在我的代码上使用片段时则高达50-60毫秒。所以，确实有显著的差异，但仍然比真正的暴力破解要快几个数量级。 - גלעד ברקן

Answer 2

这里有一个想法，参考了用户3386109在评论中的建议，但是与其将子数组的可能AND作为参数，我们将当前最高位设置为参数。

给定前缀，其中最高位为b，我们希望返回所有具有设置b的后缀的AND组合。如果没有这样的后缀，我们就不能使用这个位，所以尝试更低的位。请注意，生成具有固定最高位的所有可能分区的值将必然包括它们中的最佳答案。

下面的递归具有left_index、right_index、current_k、bth_bit_set作为参数（和搜索空间），并且具有可能值列表作为结果。我们对单个调用以及对具有固定左侧和不同右侧索引的一系列调用的聚合应用记忆化（看起来像暴力破解，不是吗？）。

JavaScript代码如下（不确定是否始终有效：）除非我犯了错误，或者很难获得退化数据，否则似乎像用户3386109建议的那样修复高位会大大减少搜索空间。

function f(arr, K){
  let str = `Array:\n${ arr.join('\n') }` + 
            `\n\nK: ${ K }\n\n`

  let hash = {
    f: {},
    f_range: {}
  }

  function g(l, r, k, b, A, K){
    // Out of bounds
    if (r > A.length - 1 || k > K || b < 0)
      return []

    if (hash.f.hasOwnProperty([l, r, k, b]))
      return hash.f[[l, r, k, b]]
      
    let s = pfxs[r] - pfxs[l-1]
    
    // This sum does not have
    // the bth bit set
    if (!(s & (1 << b)))
      return hash.f[[l, r, k, b]] = []
      
    if (r == A.length - 1){
      if (k < K)
        return hash.f[[l, r, k, b]] = []
      else
        return hash.f[[l, r, k, b]] = [s]
    }
    
    if (k == K){
      if (r == A.length - 1)
        return hash.f[[l, r, k, b]] = s & (1 << b) ? [s] : []
      else
        return hash.f[[l, r, k, b]] = g(l, r + 1, k, b, A, K)
    }
    
    // Possible suffixes
    let sfxs = []
    // Number of parts outstanding
    let ks = K - k
    // Upper bound for next part
    let ub = A.length - ks + 1
    
    if (hash.f_range.hasOwnProperty([r + 1, ub, k + 1, b])){
      sfxs = hash.f_range[[r + 1, ub, k + 1, b]]

    } else {
      for (let rr=r+1; rr<ub; rr++)
        sfxs = sfxs.concat(
          g(r + 1, rr, k + 1, b, A, K)
        )
      hash.f_range[[r + 1, ub, k + 1, b]] = sfxs
    }
        
    // We have a possible solution
    if (sfxs.length){
      result = []
      
      for (let sfx of sfxs)
        result.push(s & sfx)
      
      return hash.f[[l, r, k, b]] = result
    
    } else {
      return []
    }
  }

  // Array's prefix sums
  let pfxs = [arr[0]]
  for (let i=1; i<arr.length; i++)
    pfxs[i] = arr[i] + pfxs[i - 1]
  pfxs[-1] = 0

  let highBit = -1

  let maxNum = arr.reduce((acc, x) => acc + x, 0)
  while (maxNum){
    highBit++
    maxNum >>= 1
  }

  str += `\nhigh bit: ${ highBit }`

  let best = 0

  for (let b=highBit; b>=0; b--){
    for (let r=0; r<arr.length-K+1; r++){
      let result = g(0, r, 1, b, arr, K)
      //str += `\n${ JSON.stringify(result) }`
      if (result.length)
        best = Math.max(best, Math.max.apply(null, result))
    }
    if (best)
      break
  }
  console.log(str + '\n')
  return best
}

let arr = [30, 15, 26, 16, 21]
let K = 3
console.log(`result: ${ f(arr, K) }\n\n`)

let rand_arr = []
let rand_len = Math.ceil(Math.random() * 49)
for (let i=0; i<rand_len; i++){
  let rand_exp = ~~(Math.random() * 30)
  rand_arr[i] = Math.ceil(Math.random() * (1 << rand_exp))
}
let rand_k = Math.ceil(Math.random() * rand_len)

console.log(`result: ${ f(rand_arr, rand_k) }\n\n`)

const ex = [ 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 ]

console.log(`result: ${ f(ex, 12) }`)

样例输出

Array:
9598
15283236
121703215
80
25601067
761
7071
428732360
238244
2
176
116076
4
3517
491766404
5619908
39459923
330411
8
38

K: 5


high bit: 30

result: 4259840

更多样例输出：

Array:
3853
7668
77853
1
3
6652
166
2
5
15323609
17252
3422
1
122913
8
17
89263
21934
332522269
44900
1014
2503905
449429594
4190
3
166469508
1
898071

K: 3


high bit: 29
result: 12713984

- גלעד ברקן

---

评论不是用于长时间讨论的；此对话已被 移至聊天室。 - Samuel Liew