Split Array Largest Sum

Q: Qual é a complexidade de tempo de Split Array Largest Sum?

Tempo O(n log S) e espaço extra O(1) , em que S é a soma de nums : cada verificação gulosa é uma passagem, e o intervalo dos limites é reduzido pela metade após cada verificação. São cerca de 29 verificações quando S = 5 × 10^8 . A programação dinâmica leva tempo O(k·n²) .

Q: Por que a verificação de viabilidade é monotônica?

Se cada parte de uma divisão soma no máximo c , a mesma divisão cabe em c+1 . Portanto, quando um limite funciona, todos os limites maiores também funcionam, e as respostas formam uma sequência de nãos seguida por uma sequência de sims. A busca binária encontra o primeiro sim.

Q: A busca binária funciona com números negativos?

Não. Um valor negativo pode reduzir uma soma, então o algoritmo guloso pode fechar uma parte cedo demais, e dividir uma parte pode elevar um dos pedaços acima do todo. A programação dinâmica não faz nenhuma dessas suposições e continua correta.

DifícilBusca binária Programação dinâmica

+10

Você recebe um array nums de inteiros não negativos e um inteiro k. Divida nums em exatamente k partes, em que cada parte é uma sequência não vazia de valores vizinhos e as partes mantêm a ordem. Cada parte tem uma soma, e o custo de uma divisão é a maior dessas somas.

Retorne o menor custo que qualquer divisão em k partes pode alcançar.

Função

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

numsinteger-array: os valores não negativos, em ordem
kinteger: o número de partes contíguas em que cortá-los
Retornainteger: o menor valor possível da maior soma de partes

Restrições

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ nums.length
Cada parte contém pelo menos um valor. Uma parte cujos valores são todos 0 soma 0, o que é permitido.

Exemplos

Entrada: nums = [6, 2, 9, 4, 7, 3]k = 3
Saída: 13
Explicação: A divisão [6, 2], [9, 4], [7, 3] custa 13. Nenhuma divisão custa 12: empacotar as partes da esquerda para a direita sob 12 resulta em [6, 2], [9], [4, 7], [3], quatro partes.

Entrada: nums = [8, 1, 1, 1, 5]k = 2
Saída: 8
Explicação: O 8 fica em alguma parte, então nenhuma divisão pode custar menos que 8. [8] e [1, 1, 1, 5] somam 8.

Para ir além

Com somas prefixadas, uma verificação gulosa pode encontrar onde cada parte termina por meio de busca binária. Qual é a velocidade do método completo quando k é pequeno?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Buscar diretamente a melhor divisão custa O(k·n²), mesmo com programação dinâmica. Inverta a pergunta: k partes conseguem ficar abaixo de um limite dado? Uma única passagem gulosa responde a isso; a resposta muda de não para sim uma vez conforme o limite aumenta, e a busca binária encontra essa mudança.

Programação dinâmica sobre prefixos

Correta, mas não termina nos maiores testes

Intuição

Defina best[p][j] como o menor custo de dividir os primeiros j valores em p partes. Se a última parte for nums[i..j-1], o custo será o maior entre best[p-1][i] e a soma dessa parte, e a melhor divisão dos primeiros i valores não depende de nada à sua direita. Portanto, best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i]), com i variando de p-1 a j-1, para que cada parte contenha um valor. A linha p lê apenas a linha p-1, então duas linhas são suficientes.

O algoritmo executa até k·n²/2 etapas: cerca de 1.8 × 10^10 para n = 5000 e k = 2500.

Algoritmo

Monte prefix, em que prefix[j] é a soma dos primeiros j valores, e defina best[j] = prefix[j] para uma parte.
Para cada quantidade de partes p de 2 a k, e cada fim j de p a n, obtenha o mínimo para i de p-1 a j-1 de max(best[i], prefix[j] - prefix[i]).
Armazene esses mínimos em uma nova linha e torne-a best.
Retorne 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]

Busca binária na maior soma

Intuição

Para testar um limite c, percorra da esquerda para a direita e adicione valores à parte atual enquanto a soma permanecer dentro de c; em seguida, comece uma nova parte. Isso usa o menor número possível de partes. Em comparação com qualquer divisão válida, a primeira parte do algoritmo guloso termina pelo menos tão à direita quanto a primeira parte da outra divisão, então a parte seguinte começa na mesma posição ou mais à direita. Os valores até o fim dessa parte formam um trecho de uma parte que cabe no limite e, como não há valores negativos, a soma de um trecho nunca é maior que a soma da parte inteira. Portanto, o algoritmo guloso nunca fica para trás.

Usar menos de k partes é tão bom quanto usar k: dividir em duas uma parte com dois ou mais valores nunca aumenta uma soma. Portanto, o teste é partsNeeded(c) ≤ k.

Faça uma busca binária pelo menor limite que passe no teste, entre max(nums), pois esse valor fica em alguma parte, e sum(nums), que sempre cabe em uma única parte.

Algoritmo

Defina lo = max(nums) e hi = sum(nums).
Enquanto lo < hi, calcule mid = lo + (hi - lo) / 2.
Conte as partes gulosas com limite mid: comece com 1 parte e soma 0; quando adicionar um valor ultrapassaria mid, adicione uma parte e reinicie a soma com esse valor.
Se a contagem for no máximo k, defina hi = mid; caso contrário, defina lo = mid + 1.
Retorne 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

Armadilhas e casos extremos

Iniciar lo abaixo de max(nums). O algoritmo guloso coloca um valor maior que o limite em uma parte própria, então considera o limite 5 adequado para [1, 9] com k = 2.
Testar partsNeeded(c) == k. Para [3, 0, 4] e k = 3, o limite 4 agrupa [3, 0], [4], então nenhum limite passa.
Contar as partes a partir de 0, o que deixa cada contagem uma unidade menor.
Definir hi = mid - 1 quando mid funciona, o que perde a resposta quando ela é mid.
Iniciar o i da DP em 0. Uma célula com menos valores que partes é lida como custo 0, e [100, 1, 1] com k = 3 resulta em 2 em vez de 100.

Perguntas frequentes3

Qual é a complexidade de tempo de Split Array Largest Sum?

Tempo O(n log S) e espaço extra O(1), em que S é a soma de nums: cada verificação gulosa é uma passagem, e o intervalo dos limites é reduzido pela metade após cada verificação. São cerca de 29 verificações quando S = 5 × 10^8. A programação dinâmica leva tempo O(k·n²).

Por que a verificação de viabilidade é monotônica?

Se cada parte de uma divisão soma no máximo c, a mesma divisão cabe em c+1. Portanto, quando um limite funciona, todos os limites maiores também funcionam, e as respostas formam uma sequência de nãos seguida por uma sequência de sims. A busca binária encontra o primeiro sim.

A busca binária funciona com números negativos?

Não. Um valor negativo pode reduzir uma soma, então o algoritmo guloso pode fechar uma parte cedo demais, e dividir uma parte pode elevar um dos pedaços acima do todo. A programação dinâmica não faz nenhuma dessas suposições e continua correta.

def splitArray(nums, k):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

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

Saída Esperada