Разбить массив на m подмассивов и минимизировать максимальную сумму

Источник: https://leetcode.com/problems/split-array-largest-sum/

Дан массив nums состоящий из целочисленных положитльных элементов, и дано целое число m. Нужно разделить этот массив на m непустых непрерывных подмассивов. При этом самая максимальная сумма элементов в этих подмассивах должна быть минимизирована.

Пример 1:

Дано: nums = [7,2,5,10,8], m = 2
Результат: 18
Пояснение:
Можно разбить массив на 2 подмассива четырьмя способами. Но мы выберем разбиение на [7,2,5] и [10,8], потому что именно здесь максимальная сумма = 18, и она минимальна по сравнению с другими разбиениями.

Пример 2:

Дано: nums = [1,2,3,4,5], m = 2
Результат: 9

Пример 3:

Дано: nums = [1,4,4], m = 3
Результат: 4

Ограничения:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 106
• 1 <= m <= min(50, nums.length)

 

Идея решения 

Переформулируем эту задачу в утилитарном виде. Есть набор коробок разного размера. Порядок коробок не должен меняться, все коробки заранее известны. Коробки нужно перевезти из одного места в другое. Под перевоз коробок выделено m грузовиков. Нужно определить, какой вместимости грузовики должны быть, чтобы не ходить "порожняком".

Чтобы решить объём грузовика, мы рассуждаем так:

• грузовик должен быть не меньше, чем самая максимальная коробка;
• и не больше, чем сумма всех коробок.
• Истина будет где-то посередине.

Поэтому здесь мы применяем дихотомию (или двоичный поиск). 

Берем значение где то между максимальным элементом (нижняя граница) и суммой всех элементов (верхняя граница). И считаем, сколько грузовиков такого объёма понадобится, чтоб перевезти все коробки. 

Если грузоваиков получается больше, чем мы можем себе позволить, значит, надо рассматривать грузовики бОльшего объёма, то есть из интервала [серединка+1, верхняя граница] (серединка+1 становится нижней границей).

Если грузовиков равно или меньше, чем мы можем позволить, то возможно, они сликом большие по объёму и мы можем попробовать снизить объём и рассматривать интервал [нижняя граница, серединка-1]. Предварительно запомним нашу серединку, как потеницальный ответ.

Имплементация

class Solution {
    public int splitArray(int[] arr, int m) {
        int n = arr.length;
        int ans = -1, max = arr[0], sum = 0;

// находим максимальный элемент в массиве и сумму всех элементов в массиве
        for(int val:arr) {
            sum += val;
            max = Math.max(max, val);
        }

// искомая минимальная максимальная сумма подмассива находится в интервале
// от lo=max до hi=sum
        int lo = max, hi = sum, mid = -1;

// типичный алгоритм дихотомии (двоичного поиска)
        while(lo<=hi) {
            mid = lo + (hi-lo)/2; // считаем серединку - это может быть искомое значение capacity
// считаем на сколько подмассивов мы можем разбить исходный массив при таком capacity
            int x = parts(arr, n, mid);
// если у нас получается больше подмассивов, чем нужно, то объем слишком маленький
// увеличваем его до mid+1
            if(x>m) lo = mid + 1;
// инчаче у нас получилось массивов меньше, чем надо, или ровно столько, сколько надо
            else {
                hi = mid - 1; // если меньше, то снижаем объём до mid-1
                ans = mid; // запоминаем mid, на случай, если массивов столько, сколько надо
            }

        } // повторяем, пока возможно

        return ans; // возвращаем результат
    }

// считаем, сколько разбиений получится при заданной capacity
    public int parts(int[] arr, int n, int cap) {
// считаем первый элемент возможного разбиения
        int x = 1, sum = 0;
        for(int i=0;i<n;i++) {
            sum += arr[i]; // суммируем, пока сумма ниже заданного объёма
            if(sum>cap) { // если сумма больше заданного объёма, то у нас готов +1 элемент разбиения
                sum = arr[i]; // начинаем считать следующий элемент
                x++; // количество элементов разиения
            }
        }

        return x; // возвращаем количество элементов разбиения
    }
}