Split Array Largest Sum

Рассмотрим последнюю часть разбиения. Если первые j значений образуют p частей, последняя часть — это некоторый отрезок nums[i..j-1], а первые i значений образуют остальные p-1 частей. Стоимость — это большее из двух чисел: стоимость этих p-1 частей и сумма последнего отрезка. Какой бы ни была последняя часть, первые i значений нужно разбить с минимально возможной стоимостью, и это оптимальное разбиение не зависит от того, что находится правее. Поэтому его можно вычислить один раз и использовать повторно.

Обозначим через best[p][j] минимальную стоимость разбиения первых j значений на p частей. Для одной части выбора нет: best[1][j] — это сумма первых j значений. Для большего числа частей переберём каждую начальную позицию i последней части: best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i]), где prefix[j] — сумма первых j значений. Позиция i начинается с p-1, потому что для непустых p-1 частей нужно как минимум p-1 значений, и заканчивается на j-1, потому что последняя часть должна содержать хотя бы одно значение. Ответ — best[k][n]. Строка p использует только строку p-1, поэтому достаточно двух строк длины n+1.

В первом примере разбиение [6, 2, 9, 4] на две части может завершить первую часть после 6 (стоимость max(6, 15) = 15), после 2 (max(8, 13) = 13) или после 9 (max(17, 4) = 17), поэтому best[2][4] = 13. Затем best[3][6] рассматривает последнюю часть [7, 3] и получает max(13, 10) = 13; ни один другой вариант начала не даёт меньшую стоимость.

Проблема — в объёме вычислений. Есть k строк, n конечных позиций в каждой строке и до n начальных позиций для каждой конечной позиции: до k·n²/2 шагов. При n = 5000 и k = 2500 внутренний цикл выполняется около 1.8 × 10^10 раз: 18 секунд даже при скорости 10^9 простых операций в секунду. Эту динамику всё равно полезно знать: она не предполагает, что значения неотрицательны, поэтому продолжает работать там, где быстрый метод не справляется.

Поставим вопрос иначе. Выберем предел c и спросим: можно ли разбить nums на k частей так, чтобы сумма каждой части была не больше c? Ответ на задачу — наименьший предел, для которого ответ положительный. На этот вопрос ответить гораздо проще, чем на исходный, по двум причинам.

Во-первых, ответ даёт один жадный проход. Идём слева направо и добавляем значения в текущую часть, пока её сумма не превышает c; когда следующее значение превысит этот предел, завершаем часть и начинаем новую с этого значения. При таком разбиении используется минимально возможное число частей. Сравним его с любым другим допустимым разбиением — часть за частью. Обе первые части начинаются с первого значения, а жадный алгоритм останавливается, только когда следующее значение уже не помещается, поэтому его первая часть заканчивается не раньше. Тогда вторая часть жадного разбиения начинается не раньше второй части другого разбиения. Значения жадной части до конца той второй части составляют её фрагмент, а при отсутствии отрицательных значений сумма фрагмента не может превышать сумму целого, поэтому они помещаются, и жадный алгоритм снова доходит как минимум до того же места. Жадный алгоритм никогда не отстаёт, поэтому ему никогда не требуется больше частей.

Во-вторых, меньшее число частей, чем k, так же хорошо, как ровно k. Если жадному алгоритму требуется m < k частей, разделим на две части ту, в которой два или более значений. Суммы этих частей не превышают сумму исходной части, поскольку отрицательных значений нет, а так как n ≥ k, такая часть всегда найдётся, пока число частей не достигнет k. Значит, проверка имеет вид partsNeeded(c) ≤ k.

Теперь ключевое свойство: проверка монотонна. Если подходит предел c, то подходит и c+1, поскольку то же разбиение укладывается в больший предел. Для пределов от max(nums) до sum(nums) ответы выглядят так: нет, нет, ..., нет, да, да, ..., да, и нужно найти первое «да». Диапазон безопасен с обеих сторон: никакой предел меньше max(nums) не вместит это значение, а общая сумма всегда помещается в одну часть. Первое «да» также является реальной стоимостью, а не просто границей: если сумма ни одной части разбиения не равна c, то подошёл бы и предел c-1.

Проследим за первым примером: [6, 2, 9, 4, 7, 3] при k = 3. Пределы перебираются от 9 до 31. При пределе 20 получаем [6, 2, 9], [4, 7, 3]: 2 части, да, значит, диапазон становится от 9 до 20. При пределе 14 получаем [6, 2], [9, 4], [7, 3]: 3 части, да, диапазон — от 9 до 14. При пределе 11 получаем [6, 2], [9], [4, 7], [3]: 4 части, нет, диапазон становится от 12 до 14. При пределе 13 требуется 3 части, да, диапазон — от 12 до 13. При пределе 12 требуется 4 части, нет, поэтому ответ — 13.

Каждый проход читает n значений, а диапазон каждый раз уменьшается вдвое. При общей сумме S до 5 × 10^8 потребуется около 29 проходов по 5000 значений, то есть примерно 150000 шагов.