Maximum Sum Subarray of Size K

Q: O que é uma janela deslizante de tamanho fixo?

É um intervalo de exatamente k elementos vizinhos que se move um passo de cada vez ao longo de um array. Em vez de recalcular o intervalo do zero em cada posição, você atualiza um valor acumulado: adiciona o elemento que entra pela direita e remove aquele que sai pela esquerda. Isso transforma um trabalho de O(n·k) em O(n) .

Q: Qual é a complexidade de tempo do subarray de soma máxima de tamanho k?

Com uma janela deslizante, a complexidade é O(n) em tempo e O(1) em espaço extra: uma passagem para somar a primeira janela, depois uma adição e uma subtração por etapa. Somar cada janela separadamente custa (n-k+1) × k adições, o que é O(n·k) , cerca de 2.5 × 10^7 para n = 10^4 e k = 5000 .

Q: Em que isso é diferente do problema da subarray máxima?

Aqui, o comprimento é fixo em k , então cada candidato é uma janela, e uma soma deslizante abrange todos eles. No problema da subarray máxima, o comprimento é livre, e você precisa do algoritmo de Kadane, que decide, em cada elemento, se deve estender a sequência atual ou começar uma nova. Uma janela fixa nunca tem essa opção.

Q: As somas de prefixos também podem resolver isso?

Sim. Construa prefix[i] como a soma dos primeiros i elementos, e a janela que começa em s soma prefix[s+k] - prefix[s] . Isso também leva tempo O(n) , mas armazena n+1 totais. A janela deslizante obtém as mesmas somas com duas variáveis.

FácilJanela deslizante

+10

Você recebe um array de inteiros nums e um comprimento de janela k. Observe cada sequência de exatamente k elementos vizinhos e retorne a maior soma entre elas. Os valores podem ser negativos, então a resposta também pode ser negativa.

Função

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

numsinteger-array: o array de números inteiros
kinteger: quantos elementos vizinhos cada janela contém
Retornainteger: a maior soma de quaisquer k elementos consecutivos

Restrições

1 ≤ k ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴

Exemplos

Entrada: nums = [4, -1, 3, 7, -2, 5, 1]k = 3
Saída: 10
Explicação: As cinco janelas de comprimento 3 somam 6, 9, 8, 10 e 4. A maior é 7 + (-2) + 5 = 10.

Entrada: nums = [-3, -8, -1, -6]k = 2
Saída: -7
Explicação: Todos os valores são negativos, então todas as somas das janelas também são: -11, -9 e -7. A maior delas é -1 + (-6) = -7.

Entrada: nums = [5, -2, 4]k = 3
Saída: 7
Explicação: Quando k é igual ao comprimento do array, há uma janela, o array inteiro, e 5 + (-2) + 4 = 7.

+15 testes ocultos ao enviar

Para ir além

Você também pode retornar onde começa a melhor janela, escolhendo a mais à esquerda quando várias janelas empatarem?

Dicas

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

0 de 3 abertas

Solução

Há n-k+1 janelas, e somar cada uma do zero custa k adições. O truque é que duas janelas vizinhas se sobrepõem em todos os elementos, exceto dois. Deslize a janela em vez de reconstruí-la: um valor entra, um valor sai, e cada soma da janela custa duas operações.

Some todas as janelas

Correta, mas não termina nos maiores testes

Intuição

Uma janela é definida pelo ponto em que começa. Ela pode começar no índice 0, 1 e assim por diante até n-k, pois um início posterior ultrapassaria o fim do array. Para cada início, some os k elementos e compare o total com o melhor resultado até então.

Para [4, -1, 3, 7, -2, 5, 1] e k = 3, isso resulta nas somas 6, 9, 8, 10, 4, e a resposta é 10. Comece com o melhor resultado igual à soma da primeira janela ou ao menor número inteiro; nunca use 0: se todos os valores forem negativos, 0 seria maior que qualquer janela real.

O custo é de (n-k+1) × k adições. Ele atinge o pico quando k é aproximadamente metade de n: com n = 10^4 e k = 5000, são 5001 × 5000, cerca de 2.5 × 10^7 adições, e quase todas repetem o trabalho feito para a janela anterior.

Algoritmo

Defina best como o menor valor possível.
Para cada início de 0 a n-k, defina total = 0.
Some nums[start] até nums[start+k-1] em total.
Se total superar best, armazene-o.
Retorne best.

def maxSumSubarray(nums, k):
    n = len(nums)
    best = None
    for start in range(n - k + 1):
        total = 0
        for i in range(start, start + k):
            total += nums[i]
        if best is None or total > best:
            best = total
    return best

Deslize uma janela fixa

Intuição

Compare a janela que começa no índice 0 com a que começa no índice 1. Em [4, -1, 3, 7, -2, 5, 1] com k = 3, elas são 4 + (-1) + 3 = 6 e (-1) + 3 + 7 = 9. Ambas contêm -1 e 3. A segunda soma é a primeira mais o valor que entrou, 7, menos o valor que saiu, 4: 6 + 7 - 4 = 9.

Isso vale para cada etapa. Quando a extremidade direita da janela se move para o índice i, o elemento em i entra e o elemento em i-k sai. Então você soma a primeira janela uma vez e, em seguida, atualiza a soma com uma adição e uma subtração por etapa. As somas são 6, 9, 8, 10, 4, iguais às da força bruta, e você mantém a maior.

Cada elemento entra uma vez e sai no máximo uma vez, então o tempo é O(n). Você mantém dois números, a soma da janela atual e a melhor soma, então o espaço extra é O(1). Nenhuma soma aqui ultrapassa 10^4 × 10^4 = 10^8, então um inteiro de 32 bits é suficiente.

Algoritmo

Some nums[0] até nums[k-1] em window.
Defina best = window.
Para cada i de k até n-1, some nums[i] e subtraia nums[i-k].
Após cada etapa, defina best como o maior entre best e window.
Retorne best.

def maxSumSubarray(nums, k):
    # Sum of the first window, nums[0..k-1].
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        # Slide one step right: nums[i] enters, nums[i-k] leaves.
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best

Armadilhas e casos extremos

A ideia da janela é simples, então os bugs ficam escondidos nos valores iniciais e nos índices.

Iniciar best com 0. Com [-3, -8, -1, -6] e k = 2, a resposta real é -7, mas um best igual a 0 nunca é superado e acaba sendo retornado como resposta.
Subtrair o elemento errado. Quando nums[i] entra, o elemento que sai é nums[i-k]. Usar nums[i-k+1] ou nums[i-k-1] resulta em janelas com o comprimento errado.
Interromper a força bruta uma posição inicial antes da hora. A última janela começa em n-k, então o laço precisa incluí-la. Quando k = n, essa é a única janela, e um erro de um índice não verifica nenhuma janela e retorna o valor inicial de best.
Comparar somente depois do laço. A melhor janela pode ser a primeira, então compare também a primeira soma ou inicialize best com ela.
Esquecer que R e Lua começam a contar em 1. A primeira janela é nums[1..k], e o elemento que sai quando nums[i] entra continua sendo nums[i-k].

Perguntas frequentes4

O que é uma janela deslizante de tamanho fixo?

É um intervalo de exatamente k elementos vizinhos que se move um passo de cada vez ao longo de um array. Em vez de recalcular o intervalo do zero em cada posição, você atualiza um valor acumulado: adiciona o elemento que entra pela direita e remove aquele que sai pela esquerda. Isso transforma um trabalho de O(n·k) em O(n).

Qual é a complexidade de tempo do subarray de soma máxima de tamanho k?

Com uma janela deslizante, a complexidade é O(n) em tempo e O(1) em espaço extra: uma passagem para somar a primeira janela, depois uma adição e uma subtração por etapa. Somar cada janela separadamente custa (n-k+1) × k adições, o que é O(n·k), cerca de 2.5 × 10^7 para n = 10^4 e k = 5000.

Em que isso é diferente do problema da subarray máxima?

Aqui, o comprimento é fixo em k, então cada candidato é uma janela, e uma soma deslizante abrange todos eles. No problema da subarray máxima, o comprimento é livre, e você precisa do algoritmo de Kadane, que decide, em cada elemento, se deve estender a sequência atual ou começar uma nova. Uma janela fixa nunca tem essa opção.

As somas de prefixos também podem resolver isso?

Sim. Construa prefix[i] como a soma dos primeiros i elementos, e a janela que começa em s soma prefix[s+k] - prefix[s]. Isso também leva tempo O(n), mas armazena n+1 totais. A janela deslizante obtém as mesmas somas com duas variáveis.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

nums = [4, -1, 3, 7, -2, 5, 1]
k = 3

Esperado