ru.javascript.info icon indicating copy to clipboard operation
ru.javascript.info copied to clipboard

Массивы - Задача "Подмассив наибольшей суммы"

Open Kealstex opened this issue 4 years ago • 1 comments

решение задачи с наибольшей суммой подмассива считаю некорректным

например: [-3,4,1,7,-9, 10] исходный массив здесь наибольшая сумма по алгоритму из решения на сайте = 12 сумма(4, 1, 7) но на практике же наибольшая сумма здесь 13 сумма(4, 1,7, (-9, 10))

можно просто перебирать по индексам и с помощью ?.[] узнавать существует ли индекс после текущего. если существует, то проверить сумму ДВУХ последующих. если сумма > 0, то к этой последовательности нужно приплюсовать текущее значение, даже если оно отрицательное и последующее после него (то есть сразу два значения).

моё решение тут:

function getMaxSubSum(arr) {
    let maxSum = 0;
    let partialSum = 0;
    for (let i=0; i<arr.length-1; i++) { 

        partialSum += arr[i];
        
        //если отрицательно первое число - его нет смысл прибавлять ко второму, потому i!==0
        //если число не первое и в сумме с последующим получается положителное число, то
        // прибавляем текущее число и следующее. потому пропускаем две итерации за счет i++ и continue

        if (arr[i] < 0 && i !== 0 && arr[i] + arr?.[i+1] > 0) {
            console.log(arr[i], arr[1+i]);
            maxSum = partialSum + arr?.[i+1];
            i++;
            continue;
        }

        maxSum = Math.max(maxSum, partialSum); // запоминаем максимум на данный момент
        if (partialSum < 0) partialSum = 0; // ноль если отрицательное
    }

    return maxSum;
}

Kealstex avatar Feb 08 '21 15:02 Kealstex

решение, которое сейчас в учебнике, все правильно считает а ваше решение по-моему не учитывает последовательность нескольких отрицательных чисел например, [-3,4,1,7,-2, -3, -1, 10]

TravellerOnline avatar Jul 13 '21 19:07 TravellerOnline