Как разбить массив целых чисел таким образом, чтобы минимизировать максимум суммы каждого раздела?

Question

Входы представляют собой массив A положительных или нулевых целых чисел и другое целое число K.

Мы должны разделить A на K блоков последовательных элементов (под «разделом» я подразумеваю, что каждый элемент из A принадлежит некоторому блоку и 2 разные блоки не содержат общего элемента).

Определим сумму блока как сумму элементов блока.

Цель состоит в том, чтобы найти такой раздел в K-блоках таким образом, чтобы максимальное количество сумм каждого блока (назовем это «MaxSumBlock») сведено к минимуму.

Нам нужно вывести MaxSumBlock (нам не нужно, чтобы найти фактический раздел)

Вот пример:

Вход:

A = {2, 1, 5, 1, 2, 2, 2} 
K = 3 

Ожидаемый результат:

MaxSumBlock: 6 
(with partition: {2, 1}, {5, 1}, {2, 2, 2}) 

В ожидаемом выходе суммами каждого блока являются 3, 6 и 6. Максимальное значение равно 6.

Вот не оптимальное разбиение:

partition: {2, 1}, {5}, {1, 2, 2, 2} 

Суммы каждого блока в этом случае являются 3, 6 и 7. макс, следовательно, 7. Это не правильный ответ.

Какой алгоритм решает эту проблему?

EDIT: K и размер A не превышает 100 000. Каждый элемент A не больше 10'000

Answer 1

Используйте двоичный поиск.

Пусть максимальная сумма колеблется от 0 до суммы (массива). Итак, mid = (диапазон/2). Посмотрите, можно ли достигнуть середины путем разбиения на k в O (n) времени. Если да, перейдите для более низкого диапазона, а если нет, перейдите на более высокий диапазон.

Это даст вам результат в O (n log n).

PS: Если у вас возникли проблемы с написанием кода, я могу помочь, но я предлагаю вам попробовать сначала.

EDIT:
в соответствии с просьбой, я объясню, как найти, если mid может быть достигнуто за счет разбиения на k множеств в О (п).
Итерации через элементы до суммы меньше или равны mid. Как только он станет больше, чем mid, пусть он станет частью следующего набора. Если вы получаете k или менее, mid достижимо, иначе нет.