如何找到给定长度的两个最大不相交子阵？

Question

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

我写了一个函数，它html" target="_blank">循环a并找到a的所有长度为B的子数组和a的所有长度为C的子数组，然后找到最大的B长子数组的元素之和和最大的C长子数组的元素之和。一开始，我以为我可以把最大的c长子数组和最大的b长子数组加起来，找到38。但后来我意识到，我的函数并不确保B-long子数组和C-long子数组是不相交的，而是只找到A的长度分别为B和C的最大子数组，这是不够的。

它在上面的例子中有效，但是考虑下面的例子: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长和C长不相交子数组。然后它应该把元素加起来，得到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长和C长子数组的元素，而是求和不相交的最大B长和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;
  }