Molto probabilmente, con il codice che stai usando adesso, stai contando tutti i subarray continui dell'input: sono tanti! Di fatto sono (n*(n+1))/2 (dove n è il numero di elmenti dell'array in input). In genere si tende ad approssimare questa formula con n^2.
Adesso, mettiamo il caso che in input abbiamo 10000 elementi: stai controllando 10000^2 subarray, ovvero stai facendo 100000000 somme e controlli! (di certo non è una soluzione con un tempo d'esecuzione di 30ms).
Detto questo, serve un pò di creatività e di "trial and error" su carta per riuscire a tirare fuori l'algoritmo che va per n (ovvero, se hai 10000 elementi, fa circa 10000 controlli) senza una previa conoscenza di algoritmi, ma dovrebbe essere fattibile (ti consiglio di informarti sull'argomento "sliding window algorithm" https://www.geeksforgeeks.org/window-sliding-technique/, questo e' un problema abbastanza classico per questa categoria).Il consiglio rimane quello di fare vari tentativi su carta prima, provando anche strategie diverse, e vedendo se i conti tornano (anche con input più piccoli, come ci fu suggerito a metodi: trovare l'input più piccolo per cui è possibile confutare una teoria)
Il miglior modo per ottimizzare è per l'appunto quello di usare l'algoritmo più opportuno per risolvere il problema (che fa la differenza di tantissimo). L'altro passo consiste nel fare piccole ottimizzazioni per il codice che hai già, ponendoti qualche domanda:
- C'è qualche operazione che posso evitare in base all'input? Ad esempio, se calcoli la somma di un sottoarray, appena questa supera il subtotale termini il ciclo che fa la somma senza continuare ad aggiungere numeri (non ci sono numeri negativi, quindi la somma non puo' diminuire!), e ti eviti un sacco di operazioni, se hai ad esempio un subarray di 9000 elementi e già dai primi 3 hai superato il subtotale.
- Sto calcolando più di 2 volte la stessa cosa?
Es. lista[3, 2, 3] e subtotale = 5; il tuo algoritmo trova le somme di tutti i sottoarray, a cui diamo un nome, quindi:
a = [3]
b = [3, 2]
c = [3, 2, 3] # In questo punto ti sei calcolato 2 volte la somma del sottoarray b! C'è un modo in cui potresti evitarlo?
d = [2]
e = [2, 3]
f = [3]
L'esempio precedente era abbastanza piccolo, ma se pensi ad una lista con 10000 elementi, ti calcoli per 100 volte la somma del subarray che va dal primo elemento all'elemento 9900! Potresti provare a pensare a un modo per evitare di ricalcolare la somma degli stessi subarray!
- Ci sono casi speciali a cui devo far attenzione nell'input? In questo caso, abbiamo lo 0!
Es. lista[3, 0, 3] e subtotale = 3; I sottoinsiemi validi sono:
[3]
[3, 0]
[3]
[0, 3]
Come puoi sfruttare questa particolarità dello 0 nel nostro problema (se hai 3 zeri davanti a un sottoinsieme valido, al risultato devi aggiungere altri 3 subarray)?
Per farti capire, il 40% del mio codice (che in realtà ha una ventina di righe) è volto ad ottimizzare i casi con lo 0, portando il tempo d'esecuzione da 68ms a circa 30/40 ms.
Il consiglio principale che darei è quello di fare BENCHMARKING, in Python si fa usando https://docs.python.org/3/library/timeit.html. Se vuoi fare una modifica e vedere se effettivamente è più veloce devi eseguire il codice e vedere se effetivamente il tempo d'esecuzione è diminuito, non c'è altro modo.
Spero di esserti stato d'aiuto e di non aver scritto qualche stupidaggine , nel dubbio correggetemi. Non sono un esperto di algoritmi e di ottimizzazione, tutto quello che ho scritto è da prendere con un pizzico di sale. (Se qualcuno vuole sapere come sono arrivato a quel (n*(n+1))/2, se lo chiede, posso fare una dimostrazione)