Encontrando as somas consecutivas de um array

Question

Estou trabalhando em um desafio de codificação. O desafio basicamente quer que eu encontre a soma máxima de seus k elementos consecutivos. Aqui está um exemplo:

Para inputArray = [2, 3, 5, 1, 6]e k = 2, a saída deve ser arrayMaxConsecutiveSum(inputArray, k) = 8. Todas as somas possíveis de 2 elementos consecutivos são:

2 + 3 = 5;
3 + 5 = 8;
5 + 1 = 6;
1 + 6 = 7.

Assim, a resposta é 8.

Esta é a minha tentativa. Eu olhei para a soma consecutiva como sub-listas. Então, se eu tiver k=3, tenho que adicionar os 2 elementos após i. Portanto, se o início for o índice 0, o fim será o início + k-1. Então tentei usar um loop for para acrescentar a soma de cada k pedaços a uma nova lista. Meu objetivo final era retornar o max()desta lista:

def arrayMaxConsecutiveSum(inputArray, k):
    begin = 0
    end = begin + (k-1)
    sum_list = []
    
    for i in range(0, len(inputArray)):
        begin = i
        sum_list.append(sum(inputArray[begin:end+1]))
    
    print(sum_list)

Agora eu só queria ver como sum_listera o meu antes de tentar retornar seu máximo. No entanto, isso é o que ele retorna para um caso de teste:

Input: inputArray: [2, 3, 5, 1, 6]
k: 2
Output: null
Expected Output: 8
Console Output: [5, 3, 0, 0, 0]

Acho que minha lógica está correta. Só gostaria de saber onde é que estou errando.

Answer 1

Uma solução bastante eficiente é usar itertools.islicee zippara gerar grupos de elementos consecutivos. Isso elimina a necessidade de fatiar sua lista

consecutive_elements = zip(*(islice(inputArray, x, None) for x in range(k)))

Um exemplo do que o gerador de islices produz:

>>> [list(islice(range(5), x, None)) for x in range(3)]
[[0, 1, 2, 3, 4], [1, 2, 3, 4], [2, 3, 4]]

islice(inputArray, x, None) for x in range(k)cria iteráveis ​​a partir de sua entrada que corta um número crescente de elementos, passando isso para zipjuntar os elementos iteráveis ​​criando seus grupos

E depois use mappara gerar as somas em vez de criar uma lista intermediária

return max(map(sum, consecutive_elements))

Answer 2

Se você quiser algo mais legível e sem usar outras bibliotecas como itertools, você pode tentar este one-liner -

[sum(i) for i in zip(*(inputArray[i:] for i in range(k)))]

[5, 8, 6, 7]

---

Depurando seu código:

Tem algumas coisas erradas no código. Primeiro, você está definindo o final fora do loop. Como o início da mudança, você deseja que o final também mude no loop. Além disso, como o python já considera n-1o índice para o fim, você só precisa configurá-lo para begin+ke não begin+(k-1). Em seguida, você precisa mover o iterador de 0 para length ou array - 1, pois o último item será apenas um único elemento. Se você quiser ver onde errou, modifiquei o código para ser executado como você espera -

def arrayMaxConsecutiveSum(inputArray, k):
    #begin = 0 #<--- #No need since you are setting it to i in loop
    #end = begin + k #<--- Not to be defined here but inside loop
    sum_list = []
    
    for i in range(0, len(inputArray)-1): #<----
        begin = i
        end = begin + k #<--- 
        sum_list.append(sum(inputArray[begin:end])) #<----
    
    print(sum_list)

[5, 8, 6, 7]

Answer 3

pegue a soma do índice dado ao índice + k para (5 -(k-1)) vezes neste caso e o máximo

inputArray = [2, 3, 5, 1, 6]
k = 3
print(max([sum(inputArray[idx : idx + k]) for idx in range(len(inputArray)-(k-1))])) 

Answer 4

Você precisa atualizar seu índice final.

def arrayMaxConsecutiveSum(inputArray, k):
    begin = 0
    end = begin + k
    sum_list = []

    for i in range(0, len(inputArray)):
    
        sum_list.append(sum(inputArray[i:i + k]))

    print(sum_list)