Trovare le somme consecutive di un array

Question

Sto lavorando a una sfida di codifica. La sfida fondamentalmente vuole che io trovi la somma massima dei suoi k elementi consecutivi. Ecco un esempio:

Per inputArray = [2, 3, 5, 1, 6]e k = 2, l'output dovrebbe essere arrayMaxConsecutiveSum(inputArray, k) = 8. Tutte le possibili somme di 2 elementi consecutivi sono:

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

Quindi la risposta è 8.

Questo è il mio tentativo. Ho guardato la somma consecutiva come sotto-elenchi. Quindi, se ho k=3, devo aggiungere i 2 elementi seguenti i. Quindi se l'inizio è l'indice 0, la fine è l'inizio + k-1. Quindi ho provato a utilizzare un ciclo for per aggiungere la somma di ogni k blocchi a un nuovo elenco. Il mio obiettivo finale era quello di restituire max()da questo elenco:

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)

Ora volevo solo vedere come sum_listappariva il mio prima di provare a restituire il suo massimo. Tuttavia, questo è ciò che restituisce per un test case:

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

Penso che la mia logica sia corretta. Vorrei solo sapere dov'è che sto commettendo un errore.

Answer 1

Una soluzione abbastanza efficiente è utilizzare itertools.islicee zipgenerare gruppi di elementi consecutivi. Questo elimina la necessità di affettare la tua lista

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

Un esempio di cosa produce il generatore di islice:

>>> [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)crea iterabili dal tuo input che tagliano un numero crescente di elementi, passando questo a zipquindi si unisce agli elementi iterabili in modo saggio creando i tuoi gruppi

E poi usa mapper generare le somme piuttosto che creare una lista di intermediari

return max(map(sum, consecutive_elements))

Answer 2

Se vuoi qualcosa di più leggibile e senza usare altre librerie come itertools, puoi provare questo one-liner -

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

[5, 8, 6, 7]

---

Debug del tuo codice:

Ci sono alcune cose che non vanno nel codice. Innanzitutto, stai definendo la fine al di fuori del ciclo. Quando inizia il cambiamento, vuoi che anche la fine cambi nel ciclo. Inoltre, poiché python considera già n-1index for end, devi solo impostarlo su begin+ke non begin+(k-1). Successivamente, è necessario spostare l'iteratore da 0 a length o array - 1 poiché l'ultimo elemento sarà solo un singolo elemento. Se vuoi vedere dove hai sbagliato, ho modificato il codice per eseguirlo come ti aspetti -

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

prendi la somma da dato indice a indice + k per (5 -(k-1)) volte in questo caso e il max

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

Devi aggiornare il tuo indice finale.

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)