Split Array Largest Sum

Q: Какова временная сложность задачи «Разделение массива с минимизацией наибольшей суммы»?

Времени O(n log S) и дополнительной памяти O(1) , где S — сумма nums : каждая жадная проверка выполняется за один проход, а диапазон ограничений после каждой проверки уменьшается вдвое. Это примерно 29 проверок при S = 5 × 10^8 . Для DP требуется время O(k·n²) .

Q: Почему проверка осуществимости монотонна?

Если сумма каждой части разбиения не превышает c , то это же разбиение подходит и для c+1 . Значит, если ограничение подходит, то подойдут и все большие ограничения, поэтому сначала идут ответы «нет», а затем — ответы «да». Бинарный поиск находит первое «да».

Q: Работает ли бинарный поиск с отрицательными числами?

Нет. Отрицательное значение может уменьшить сумму, поэтому жадный алгоритм может закрыть часть слишком рано, а разбиение части может привести к тому, что один фрагмент превысит целое. В динамическом программировании не делается ни одно из этих предположений, поэтому оно остаётся корректным.

СложноБинарный поиск Динамическое программирование

+10

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

Верните наименьшую стоимость, которую можно получить при разбиении на k частей.

Функция

splitArray(nums: integer-array, k: integer) → integer

numsinteger-array: неотрицательные значения по порядку
kinteger: количество непрерывных частей, на которые нужно их разрезать
Возвращаетinteger: наименьшее возможное значение суммы самой большой части

Ограничения

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ nums.length
Каждая часть содержит как минимум одно значение. Сумма значений части, состоящей только из 0, равна 0, и это допустимо.

Примеры

Ввод: nums = [6, 2, 9, 4, 7, 3]k = 3
Вывод: 13
Пояснение: Разбиение на части [6, 2], [9, 4], [7, 3] стоит 13. Ни одно разбиение не стоит 12: упаковка частей слева направо при ограничении 12 даёт [6, 2], [9], [4, 7], [3] — четыре части.

Ввод: nums = [8, 1, 1, 1, 5]k = 2
Вывод: 8
Пояснение: 8 находится в одной из частей, поэтому ни одно разбиение не может стоить меньше 8. [8] и [1, 1, 1, 5] в сумме дают 8.

Дополнительный вопрос

С помощью префиксных сумм жадная проверка может найти конец каждой части бинарным поиском. Насколько быстрым становится весь метод, когда k мало?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Непосредственный поиск оптимального разбиения требует O(k·n²) операций даже при использовании динамического программирования. Поставим вопрос иначе: могут ли k частей уложиться в заданный предел? Один жадный проход даст ответ: по мере увеличения предела он один раз меняется с «нет» на «да», а бинарный поиск находит этот переход.

Динамическое программирование по префиксам

Верно, но не успевает на самых больших тестах

Идея

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

Алгоритм выполняет до k·n²/2 шагов: около 1.8 × 10^10 при n = 5000 и k = 2500.

Алгоритм

Постройте prefix, где prefix[j] — сумма первых j значений, и установите best[j] = prefix[j] для одной части.
Для каждого количества частей p от 2 до k и каждого конца j от p до n найдите минимум по i от p-1 до j-1 для max(best[i], prefix[j] - prefix[i]).
Сохраните эти минимумы в новой строке и сделайте её best.
Верните best[n].

def splitArray(nums, k):
    n = len(nums)
    # prefix[j] is the sum of the first j values
    prefix = [0] * (n + 1)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x
    # best[j]: the smallest largest part when the first j values form one part
    best = prefix[:]
    for parts in range(2, k + 1):
        nxt = [0] * (n + 1)
        for j in range(parts, n + 1):
            lowest = prefix[j]  # never worse than one part holding everything
            for i in range(parts - 1, j):
                # the first i values form parts-1 parts, nums[i..j-1] is the last part
                worst = max(best[i], prefix[j] - prefix[i])
                if worst < lowest:
                    lowest = worst
            nxt[j] = lowest
        best = nxt
    return best[n]

Бинарный поиск по наибольшей сумме

Идея

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

Меньше k частей — не хуже, чем k: если разделить часть из двух или более значений на две, сумма не увеличится. Поэтому условие проверки — partsNeeded(c) ≤ k.

Бинарным поиском найдите наименьшую подходящую верхнюю границу между max(nums), поскольку это значение входит в какую-либо часть, и sum(nums), которое всегда помещается в одну часть.

Алгоритм

Установи lo = max(nums) и hi = sum(nums).
Пока lo < hi, вычисляй mid = lo + (hi - lo) / 2.
Подсчитай жадные части для mid: начни с 1 части и суммы 0; если при добавлении значения сумма превысит mid, добавь часть и начни сумму заново с этого значения.
Если количество не превышает k, установи hi = mid; иначе установи lo = mid + 1.
Верни lo.

def splitArray(nums, k):
    def parts_needed(cap):
        # Fill each part left to right and start a new one only when the next value would pass cap.
        parts, current = 1, 0
        for x in nums:
            if current + x > cap:
                parts += 1
                current = x
            else:
                current += x
        return parts

    lo, hi = max(nums), sum(nums)  # one value per part at best, everything in one part at worst
    while lo < hi:
        mid = (lo + hi) // 2
        if parts_needed(mid) <= k:
            hi = mid  # mid works, so the answer is mid or smaller
        else:
            lo = mid + 1  # mid needs more than k parts, so the answer is larger
    return lo

Ловушки и крайние случаи

Начало поиска с lo ниже max(nums). Жадный алгоритм помещает значение, превышающее ограничение, в отдельную часть, поэтому считает ограничение 5 подходящим для [1, 9] при k = 2.
Проверка partsNeeded(c) == k. Для [3, 0, 4] и k = 3 при ограничении 4 получаются части [3, 0], [4], поэтому ни одно ограничение не подходит.
Подсчёт частей начиная с 0, из-за чего каждый результат на единицу меньше.
Присваивание hi = mid - 1, когда mid подходит, из-за чего ответ теряется, если он равен mid.
Начало DP с i, равного 0. Для ячейки, в которой значений меньше, чем частей, стоимость принимается равной 0, и для [100, 1, 1] при k = 3 получается 2 вместо 100.

Частые вопросы3

Какова временная сложность задачи «Разделение массива с минимизацией наибольшей суммы»?

Времени O(n log S) и дополнительной памяти O(1), где S — сумма nums: каждая жадная проверка выполняется за один проход, а диапазон ограничений после каждой проверки уменьшается вдвое. Это примерно 29 проверок при S = 5 × 10^8. Для DP требуется время O(k·n²).

Почему проверка осуществимости монотонна?

Если сумма каждой части разбиения не превышает c, то это же разбиение подходит и для c+1. Значит, если ограничение подходит, то подойдут и все большие ограничения, поэтому сначала идут ответы «нет», а затем — ответы «да». Бинарный поиск находит первое «да».

Работает ли бинарный поиск с отрицательными числами?

Нет. Отрицательное значение может уменьшить сумму, поэтому жадный алгоритм может закрыть часть слишком рано, а разбиение части может привести к тому, что один фрагмент превысит целое. В динамическом программировании не делается ни одно из этих предположений, поэтому оно остаётся корректным.

def splitArray(nums, k):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

nums = [6, 2, 9, 4, 7, 3]
k = 3

Ожидаемый вывод