Leetcode Challenge

[Решение 4.1. Разделяй и властвуй] Leetcode #53. Maximum Subarray

Условие задачи: https://yangx.top/leetcode_furrycat/28

Стратегия "Разделяй и властвуй" предполагает деление исходного массива на несколько частей. Мы будем делить на три (левую L, правую R и центральный элемент `mid`). Тогда наш искомый подмассив с максимальной суммой может лежать:

- полностью в левой части L (от 0 до `mid-1`)
- полностью в правой части R (от mid+1 до `n.length-1`)
- либо включает в себя обязательно центральный элемент mid и возможно части L и R, которые находятся рядом с mid

Для L и R мы запустим рекурсивное вычисление. Для третьего случая посчитаем максимальную сумму. Потом сравним три значения и вернем максимальное.


function getMaxSubArraySum(nums, left, right) {
    left = left ?? 0; // начало анализируемого подмассива
    right = right ?? nums.length - 1; // конец анализируемого подмассива

    if (left > right) return -Infinity;

    const mid = Math.floor((left + right) / 2); // середина анализируемого подмассива

    // рекурсивно считаем для левой и правой частей
    const maxLeftSubArraySum = getMaxSubArraySum(nums, left, mid - 1);
    const maxRightSubArraySum = getMaxSubArraySum(nums, mid + 1, right);

    // находим подмассив с максимальной суммой, 
    // который содержит элемент mid 

    let leftMaxSum = 0;
    let rightMaxSum = 0;

    // для L идем с конца, так как подмассив должен быть рядом с mid
    // считаем непрерывную сумму элементов и отбираем максимальную

    for (let i = mid - 1, currentLeftSum = 0; i >= left; i--) {
        currentLeftSum += nums[i];
        leftMaxSum = Math.max(leftMaxSum, currentLeftSum);
    }

    // то же для R 

    for (let i = mid + 1, currentRightSum = 0; i <= right; i++) {
        currentRightSum += nums[i];
        rightMaxSum = Math.max(rightMaxSum, currentRightSum);
    }

    const maxCenterSubArraySum = leftMaxSum + nums[mid] + rightMaxSum;

    return Math.max(maxLeftSubArraySum, maxRightSubArraySum, maxCenterSubArraySum)
}

Временная сложность этого решения - ожидаемо O (n * log n). Мы делаем log n разделений и для каждого считаем maxCenterSubArraySum, что требует перебора массива (n).

Пространственная сложность: O (log n) - так как у нас рекурсия.

#medium #arrays #divideandconquer #recursion

@leetcode_furrycat