Задача: 410. Split Array Largest Sum
Сложность: easy

Учитывая целочисленный массив nums и целое число k, разбейте nums на k непустых подмассивов так, чтобы наибольшая сумма любого подмассива была минимальна. Верните минимизированную наибольшую сумму разбиения. Подмассив - это смежная часть массива.

Пример:

Input: nums = [7,2,5,10,8], k = 2
Output: 18

👨‍💻 Алгоритм:

1⃣Определите границы для бинарного поиска: минимальная сумма равна максимальному элементу массива, максимальная сумма равна сумме всех элементов массива.

2⃣Выполните бинарный поиск по этим границам. Для каждой средней суммы проверьте, можно ли разбить массив на k подмассивов, чтобы максимальная сумма подмассива не превышала эту среднюю сумму.

3⃣Если возможно разбить массив для данной средней суммы, уменьшите верхнюю границу. Если нет, увеличьте нижнюю границу. Повторяйте до тех пор, пока границы не сойдутся.

😎 Решение:

function splitArray($nums, $k) {
    $left = max($nums);
    $right = array_sum($nums);
    while ($left < $right) {
        $mid = intdiv($left + $right, 2);
        if (canSplit($nums, $k, $mid)) {
            $right = $mid;
        } else {
            $left = $mid + 1;
        }
    }
    return $left;
}

function canSplit($nums, $k, $maxSum) {
    $currentSum = 0;
    $subarrays = 1;
    foreach ($nums as $num) {
        if ($currentSum + $num > $maxSum) {
            $currentSum = $num;
            $subarrays++;
            if ($subarrays > $k) {
                return false;
            }
        } else {
            $currentSum += $num;
        }
    }
    return true;
}

Ставь 👍 и забирай 📚 Базу знаний