C'è un array A
contenente numeri interi (positivi e negativi). Trova un sottoarray (contigua) la cui somma assoluta elementi è minimo, ad es .:Ricerca della somma assoluta minima di un sottoarray
A = [2, -4, 6, -3, 9]
|(−4) + 6 + (−3)| = 1 <- minimal absolute sum
Ho iniziato mediante l'attuazione di un algoritmo a forza bruta che era O(N^2)
o O(N^3)
, anche se ha prodotto risultati corretti. Ma il compito specifica:
complexity:
- expected worst-case time complexity is O(N*log(N))
- expected worst-case space complexity is O(N)
Dopo qualche ricerca ho pensato che forse l'algoritmo di Kadane può essere modificato per adattarsi a questo problema, ma non sono riuscito a farlo.
La mia domanda è: l'algoritmo di Kadane è la giusta via da seguire? In caso contrario, potresti indicarmi la direzione giusta (o nominare un algoritmo che potrebbe aiutarmi qui)? Non voglio un codice pronto, ho solo bisogno di aiuto per trovare il giusto algoritmo.
Non sto seguendo come si identifica il sottoarray dalle somme parziali. per esempio l'array [-4,5, -1] ha somme parziali [-4,1,0], che sembra implicare che il sottoarray dovrebbe essere [5, -1] = 4, mentre la soluzione effettiva è [-4,5, -1] = 0. – Benubird
Non ho considerato l'intero array, considerato come un sotto-array. Potresti considerare i subarray con piccole somme parziali separatamente o assicurarti di includere il sotto-array con zero elementi al momento di ordinare tutto - questo ha una somma pari a zero, quindi nel tuo esempio avresti somme parziali [-4, 1,0,0] e individuare la soluzione che deriva dal considerare lo span tra la fine dei termini sommati dalle due somme zero - l'inizio e la fine dell'intero array. Il sottoarray identificato da due somme parziali è l'insieme di elementi nella somma parziale con la maggior parte degli articoli sommati ma non nell'altro. – mcdowella
Considera 3,3,3,4,5? Forse sono confuso. – Catalyst