Split Array Largest Sum

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

A busca binária é executada em tempo O(n log S) , em que n é o comprimento de nums e S é a soma de seus elementos. Cada verificação gulosa percorre o array uma vez, e o intervalo dos limites máximos é reduzido pela metade após cada verificação: cerca de 29 verificações quando S = 5 × 10^8 . Ela usa espaço extra O(1) . A programação dinâmica tem tempo O(k·n²) e espaço O(n) .

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

Se cada parte de alguma divisão soma no máximo c , essa mesma divisão também tem cada parte no máximo c+1 . Portanto, quando um limite funciona, todos os limites maiores também funcionam; e, quando um limite falha, todos os limites menores também falham. As respostas formam uma sequência de “não” seguida por uma sequência de “sim”, que é exatamente o que a busca binária precisa para encontrar o limite.

Q: Por que a verificação gulosa encontra o menor número de partes?

O algoritmo guloso continua adicionando valores a uma parte até que o próximo ultrapasse o limite. Compare-o com qualquer divisão válida, parte por parte. Cada parte gulosa começa na mesma posição ou depois da parte da outra divisão com o mesmo número, então seus valores até o fim dessa parte formam um trecho de uma parte que cabe no limite. Nenhum valor é negativo, então o trecho também cabe, e o algoritmo guloso avança pelo menos tanto quanto ela. O algoritmo guloso nunca fica para trás, portanto cobre o array com o menor número de partes possível, como qualquer divisão.

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

Não. Com valores negativos, adicionar um valor pode diminuir uma soma, então o algoritmo guloso pode fechar uma parte cedo demais e deixar passar uma divisão que funciona. Dividir uma parte também pode elevar a soma de um dos trechos acima da soma do todo, então ter menos de k partes já não significa que k partes funcionam. A programação dinâmica não faz nenhuma dessas suposições e continua correta, com tempo O(k·n²) .

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 sua 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 soma da maior parte

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] tem somas 8, 13 e 10, portanto seu custo é 13. Nenhuma divisão tem custo 12: ao agrupar as partes da esquerda para a direita, com cada soma no máximo 12, obtemos [6, 2], [9], [4, 7], [3], quatro partes, quando só três são permitidas.

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

+20 testes ocultos ao enviar

Para ir além

Cada verificação gulosa lê todos os valores de n. Com somas de prefixo, uma verificação pode encontrar onde cada parte termina usando busca binária. Qual é a velocidade do método inteiro quando k é pequeno e nums é longo?

Dicas

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

0 de 3 abertas

Solução

As duas exigências entram em conflito: você precisa usar exatamente k partes e quer que a maior parte seja a menor possível. Tentar todos os lugares para os k-1 cortes explode em possibilidades, e um programa dinâmico sobre prefixos reduz isso para O(k·n²), ainda lento demais para 5000 valores. A ideia rápida inverte a pergunta. Em vez de buscar a melhor divisão, tente um limite máximo e pergunte se é possível manter k partes abaixo dele. Uma única passagem gulosa responde a isso; as respostas só mudam uma vez à medida que o limite aumenta, e a busca binária encontra essa mudança em cerca de 29 passagens.

Programação dinâmica sobre prefixos

Correta, mas não termina nos maiores testes

Intuição

Observe a última parte de uma divisão. Se os primeiros j valores formam p partes, a última parte é algum trecho nums[i..j-1], e os primeiros i valores formam as outras p-1 partes. O custo é o maior entre dois números: o custo dessas p-1 partes e a soma do último trecho. Seja qual for o último trecho, você quer dividir os primeiros i valores da forma mais barata possível, e essa melhor divisão não depende de nada à sua direita. Portanto, você pode calculá-la uma vez e reutilizá-la.

Use best[p][j] para representar o menor custo de dividir os primeiros j valores em p partes. Para uma parte, não há escolha: best[1][j] é a soma dos primeiros j valores. Para mais partes, experimente cada início i da última parte: best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i]), em que prefix[j] é a soma dos primeiros j valores. O início i vai de p-1, pois p-1 partes não vazias precisam de pelo menos p-1 valores, até j-1, pois a última parte precisa ter um valor. A resposta é best[k][n]. A linha p só lê a linha p-1, então duas linhas de comprimento n+1 são suficientes.

No primeiro exemplo, dividir [6, 2, 9, 4] em duas partes pode terminar a primeira parte após 6 (custo max(6, 15) = 15), após 2 (max(8, 13) = 13) ou após 9 (max(17, 4) = 17), então best[2][4] = 13. Em seguida, best[3][6] testa a última parte [7, 3] e obtém max(13, 10) = 13, que não é superado por nenhum outro início.

O problema é o trabalho necessário. Há k linhas, n finais por linha e até n inícios por final: até k·n²/2 passos. Com n = 5000 e k = 2500, o loop interno é executado cerca de 1.8 × 10^10 vezes: 18 segundos mesmo a 10^9 passos simples por segundo. Ainda vale a pena conhecer a DP: ela nunca pressupõe que os valores sejam não negativos, então continua funcionando nos casos em que o método rápido não funciona.

Algoritmo

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

Inverta a pergunta. Escolha um limite c e pergunte: é possível dividir nums em k partes, com a soma de cada parte no máximo c? A resposta para o problema é o menor limite para o qual a resposta é sim. Essa pergunta é muito mais fácil que a original, por dois motivos.

Primeiro, uma única passagem gulosa responde à pergunta. Percorra da esquerda para a direita e continue adicionando valores à parte atual enquanto a soma permanecer dentro de c; quando o próximo valor ultrapassar c, feche a parte e comece outra com esse valor. Isso usa o menor número de partes que qualquer divisão sob esse limite pode usar. Compare com qualquer outra divisão válida, parte por parte. As duas primeiras partes começam no primeiro valor, e o algoritmo guloso só para quando o próximo valor não cabe, então sua primeira parte termina pelo menos tão à direita quanto a outra. A segunda parte do algoritmo guloso começa então no mesmo ponto ou depois da segunda parte da outra divisão. Os valores dela até o fim dessa parte são um trecho dela e, como não há valores negativos, um trecho nunca soma mais que o todo; assim, eles cabem, e o algoritmo guloso novamente alcança pelo menos o mesmo ponto. O algoritmo guloso nunca fica para trás, então nunca precisa de mais partes.

Segundo, menos partes que k são tão boas quanto exatamente k. Se o algoritmo guloso precisar de m < k partes, divida em duas uma parte que contenha dois ou mais valores. Seus trechos somam no máximo o mesmo que o todo, porque nenhum valor é negativo, e, como n ≥ k, sempre há uma parte assim até chegar a k. Portanto, o teste é partsNeeded(c) ≤ k.

Agora, a propriedade principal: o teste é monotônico. Se o limite c funciona, c+1 também funciona, pois a mesma divisão continua cabendo sob um limite maior. Para os limites de max(nums) a sum(nums), as respostas são não, não, ..., não, sim, sim, ..., sim, e você quer o primeiro sim. O intervalo é seguro nas duas extremidades: nenhum limite abaixo de max(nums) consegue comportar esse valor, e o total sempre cabe em uma parte. O primeiro sim também é um custo real, não apenas um limite: se nenhuma parte da divisão somar exatamente c, o limite c-1 também funcionaria.

Acompanhe o primeiro exemplo, [6, 2, 9, 4, 7, 3] com k = 3. Os limites vão de 9 a 31. O limite 20 agrupa [6, 2, 9], [4, 7, 3]: 2 partes, sim, então o intervalo passa a ser de 9 a 20. O limite 14 resulta em [6, 2], [9, 4], [7, 3]: 3 partes, sim, intervalo de 9 a 14. O limite 11 resulta em [6, 2], [9], [4, 7], [3]: 4 partes, não, intervalo de 12 a 14. O limite 13 precisa de 3 partes, sim, intervalo de 12 a 13. O limite 12 precisa de 4, não, então a resposta é 13.

Cada passagem lê n valores e o intervalo cai pela metade a cada vez. Com um total S de até 5 × 10^8, isso dá cerca de 29 passagens por 5000 valores, aproximadamente 150000 etapas.

Algoritmo

Defina lo = max(nums) e hi = sum(nums).
Enquanto lo < hi, calcule mid = lo + (hi - lo) / 2.
Conte as partes necessárias pelo método guloso sob o limite mid: comece com 1 parte e uma soma acumulada de 0; quando adicionar um valor ultrapassar 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

A busca é curta, então os bugs estão na verificação gulosa e nos limites.

Começar lo abaixo de max(nums). A verificação gulosa coloca um valor maior que o limite em uma parte própria e continua, então informa que um limite de 5 é suficiente para [1, 9] com k = 2. Comece pelo maior valor ou faça a verificação falhar quando um único valor exceder o limite.
Testar partsNeeded(c) == k. Muitas vezes, o algoritmo guloso precisa de menos partes que k: para [3, 0, 4] e k = 3, o limite 4 agrupa [3, 0], [4]. Com ==, nenhum limite passa. Sempre é possível dividir ainda mais quando há menos partes, então teste ≤ k.
Contar as partes a partir de 0. A primeira parte existe antes que qualquer valor faça com que ela ultrapasse o limite, então a contagem começa em 1.
Definir hi = mid - 1 quando mid funciona. Isso pode ignorar a própria resposta. Mantenha hi = mid e faça o loop enquanto lo < hi.
Começar o i da DP em 0. Uma célula best[i] com i < p-1 representa menos valores do que partes, o que nenhuma divisão pode fazer, e, em uma linha preenchida com zeros, ela é lida como custo 0. Para [100, 1, 1] com k = 3, a DP então informa 2 em vez de 100. Comece i em p-1.
Estouro com limites maiores. Aqui, o total é no máximo 5 × 10^8, então inteiros de 32 bits são suficientes. Se os valores chegarem a 10^6, 2148 deles já ultrapassam 2^31-1, então use somas de 64 bits.

Perguntas frequentes4

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

A busca binária é executada em tempo O(n log S), em que n é o comprimento de nums e S é a soma de seus elementos. Cada verificação gulosa percorre o array uma vez, e o intervalo dos limites máximos é reduzido pela metade após cada verificação: cerca de 29 verificações quando S = 5 × 10^8. Ela usa espaço extra O(1). A programação dinâmica tem tempo O(k·n²) e espaço O(n).

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

Se cada parte de alguma divisão soma no máximo c, essa mesma divisão também tem cada parte no máximo c+1. Portanto, quando um limite funciona, todos os limites maiores também funcionam; e, quando um limite falha, todos os limites menores também falham. As respostas formam uma sequência de “não” seguida por uma sequência de “sim”, que é exatamente o que a busca binária precisa para encontrar o limite.

Por que a verificação gulosa encontra o menor número de partes?

O algoritmo guloso continua adicionando valores a uma parte até que o próximo ultrapasse o limite. Compare-o com qualquer divisão válida, parte por parte. Cada parte gulosa começa na mesma posição ou depois da parte da outra divisão com o mesmo número, então seus valores até o fim dessa parte formam um trecho de uma parte que cabe no limite. Nenhum valor é negativo, então o trecho também cabe, e o algoritmo guloso avança pelo menos tanto quanto ela. O algoritmo guloso nunca fica para trás, portanto cobre o array com o menor número de partes possível, como qualquer divisão.

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

Não. Com valores negativos, adicionar um valor pode diminuir uma soma, então o algoritmo guloso pode fechar uma parte cedo demais e deixar passar uma divisão que funciona. Dividir uma parte também pode elevar a soma de um dos trechos acima da soma do todo, então ter menos de k partes já não significa que k partes funcionam. A programação dinâmica não faz nenhuma dessas suposições e continua correta, com tempo O(k·n²).

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado