Как найти два самых больших непересекающихся подмассива заданной длины? - PullRequest
Новая
       27

Как найти два самых больших непересекающихся подмассива заданной длины?

1 голос
/ 24 мая 2019

Мне нужно написать функцию, которая принимает в качестве входных данных массив A целых положительных чисел, целых положительных чисел B и целых положительных чисел C. Затем функция должна возвращать общую сумму элементов двух непересекающихся подмассивов A длиныB и C, которые максимизируют такую ​​сумму.Например, если A = [3, 11, 1, 2, 9, 4, 5, 6, 1], B = 4 и C = 2, то функция должна вернуть 38. Это потому, что два самых больших непересекающихся подмассиваА длины B и C имеют значения [9, 4, 5, 6] и [3, 11].Сумма элементов первого подмассива равна 9 + 4 + 5 + 6 = 24, а сумма элементов второго подмассива равна 3 + 11 = 14, поэтому общая сумма двух подмассивов равна 38.

Iнаписал функцию, которая проходит через A и находит все подмассивы A длины B и все подмассивы A длины C, а затем находит сумму элементов наибольшего подмассива B-длины и сумму элементовсамый большой C-длинный подмассив.Сначала я подумал, что могу просто суммировать самый большой подмассив C-long и самый большой подмассив B-long, чтобы найти 38. Но потом я понял, что моя функция не гарантирует, что подмассив B-long и C-long будетдизъюнкт, но вместо этого просто находит самые большие подмассивы A длины B и C соответственно, что недостаточно.

Это работает в приведенном выше примере, но рассмотрим следующий пример: A = [3, 7, 10, 5, 2, 1, 3, 4], B = 4, C = 2. Здесь простоНахождение наибольшего подмассива B-long и наибольшего подмассива C-long даст [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. Другими словами, когда самые большие подмассивы A длины B и C перекрываются, функция должна найти комбинацию таких подмассивов B-long и C-long, которая максимизирует окончательную суммуэлементы.Это мой код до сих пор: 

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

Как я могу исправить это, чтобы убедиться, что функция не суммирует элементы самых больших B-длинных и C-длинных подмассивов A, а вместо этогосуммирует элементы самых больших подмассивов DISJOINT B-long и C-long (два, которые максимизируют окончательную сумму)?

Ответы [ 2 ]

0 голосов
/ 24 мая 2019

Вы можете сначала получить массив для каждой суммы подмножества, а затем проверить индексы и взять только суммы из индексов, которые не перекрываются. 

function getSums(array, size) {
    var sum = array.slice(0, --size).reduce((a, b) => a + b, 0);
    return array.slice(size).map((v, i) => sum += v - (array[i - 1] || 0));
}

function solution(array, ...sizes) {
    var sums = sizes.map(l => getSums(array, l)),
        i, j,
        max = 0;

    for (i = 0; i < sums[0].length; i++) {
        for (j = 0; j < sums[1].length; j++) {
            if (j >= i + sizes[0] || j + sizes[1] <= i) {
                max = Math.max(max, sums[0][i] + sums[1][j]);
            }
        }
    }
    return max;
}

console.log(solution([3, 11, 1, 2, 9, 4, 5, 6, 1], 4, 2));
console.log(solution([3, 7, 10, 5, 2, 1, 3, 4], 4, 2));
0 голосов
/ 24 мая 2019 
   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;
  }
...