Допустим, у нас есть массив целых: a = {2,4,3,5}

И у нас есть к = 3.

Мы можем разбить массив a на k (3) подмассивы, в которых порядок массива не может быть изменен. Сумма каждого вложенного массива должна быть как можно ниже, чтобы максимальная сумма среди всех вложенных массивов была как можно меньше.

Для приведенного выше решения это даст {2, 4}, {3}, {5} с максимальной суммой 6 (4 + 2).

Неправильный ответ: {2}, {4, 3}, {5}, поскольку в этом случае максимальная сумма равна 7 (4 + 3).

Я попытался создать жадный алгоритм, который вычисляет среднее значение для всего массива путем суммирования всех целых и деления его на результирующее количество вложенных массивов. Таким образом, в приведенном выше примере это будет означать 14/3 = 4 (целочисленное деление). Затем он будет складывать числа в счетчик, пока он <меньше среднего числа. Затем он пересчитает оставшуюся часть подмассива.

Мое решение дает хорошее приближение и может использоваться как эвристическое, но не всегда дает мне правильный ответ.

Может ли кто-нибудь помочь мне с алгоритмом, который дает мне оптимальное решение для всех случаев и лучше, чем O (N²)? Я ищу алгоритм, который является O (N журнала N) примерно.

Заранее спасибо!