javascript - 如何找到给定长度的两个最大的不相交子数组？

Question

我需要编写一个函数，将正整数数组 A、正整数 B 和正整数 C 作为输入。然后，该函数应返回长度为 B 和 C 的 A 的两个不相交子数组的元素的总和，使该总和最大化。例如，如果 A = [3, 11, 1, 2, 9, 4, 5, 6, 1]，B = 4 且 C = 2，则函数应返回 38。这是因为长度 B 和 C 的 A 是 [9, 4, 5, 6] 和 [3, 11]。第一个子数组的元素之和为9+4+5+6=24，第二个子数组的元素之和为3+11=14，所以两个子数组的总和为38。

我写了一个函数，循环遍历A，找到A的所有长度为B的子数组和A的所有长度为C的子数组，然后求最大B长子数组的元素之和和最大的 C 长子数组的元素。起初我以为我可以将最大的 C-long 子数组和最大的 B-long 子数组加起来找到 38。但是后来我意识到我的函数并不能确保 B-long 子数组和 C-long 子数组是不相交，而只是分别找到长度为 B 和 C 的 A 的最大子数组，这是不够的。

它在上面的例子中有效，但考虑下面的例子:A = [3, 7, 10, 5, 2, 1, 3, 4], B = 4, C = 2。在这里，仅仅找到最大的 B 长子数组和最大的 C 长子数组将产生 [3, 7, 10, 5] 和 [7, 10]。然后该函数将继续对 3+7+10+5=25 和 7+10=17 求和并返回 38。但这不行，因为这两个子数组不是不相交的子数组。该函数应该返回 [3, 7, 10, 5] 和 [3,4] 作为最大的 B-long 和 C-long 不相交子数组。然后它应该对元素求和得到32。换句话说，当长度为B和C的A的最大子数组重叠时，函数应该找到这样的B长和C长子数组的组合，使得最终的和最大化要素。到目前为止，这是我的代码:

function solution(A, B, C) {
var groupB = [];
var sumgroupB;
var maxSumArrayB;
var valuesSumsBArray = [];
if (A.length < (B + C)) {
    return -1;
} else {
    for (var i = 0; i < A.length; i++) {
        if (i+B<=A.length) {
        groupB = A.slice(i, i+B);
        sumgroupB = groupB.reduce(function sum(a, b) { return a+b} );
        valuesSumsBArray.push(sumgroupB);
        }
    }
    maxSumArrayB = Math.max(...valuesSumsBArray);
}


var groupC = [];
var sumgroupC;
var maxSumArrayC;
var valuesSumsCArray = [];
if (A.length < (B + C)) {
    return -1;
} else {
    for (var i = 0; i < A.length; i++) {
        if (i+C<=A.length) {
        groupC = A.slice(i, i+C);
        sumgroupC = groupC.reduce(function sum(a, b) { return a+b} );
        valuesSumsCArray.push(sumgroupC);
        }
    }
    maxSumArrayC = Math.max(...valuesSumsCArray);
}

return [maxSumArrayB, maxSumArrayC];

}
console.log(solution([3, 11, 1, 2, 9, 4, 5, 6, 1], 4, 2)) 

我怎样才能修复它以确保该函数不会对 A 的最大 B-long 和 C-long 子数组的元素求和，而是对最大 DISJOINT B-long 和 C 的元素求和- 长子数组(最大化最终总和的两个子数组)？

Answer 1

   function solution(A, B, C) {
     let max = -Infinity;

     for(let startB = 0; startB < A.length - B; startB++) {
       // C is before B
      for(let startC = 0; startC + C < startB; startC++) {
         const sum = [...A.slice(startC, startC + C), ...A.slice(startB, startB + B)].reduce((a, b) => a + b, 0);
         if(sum > max) max = sum;
      }
        // C is behind B
      for(let startC = startB + B; startC < A.length; startC++) {
         const sum = [...A.slice(startC, startC + C), ...A.slice(startB, startB + B)].reduce((a, b) => a + b, 0);
         if(sum > max) max = sum;
      }
    }

    return max;
  }