8

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.

risposta

14

Se si calcola le somme parziali tali come

2, 2 +(-4), 2 + (-4) + 6, 2 + (-4) + 6 + (-3)... 

Poi la somma di qualsiasi sottoarray contiguo è la differenza di due delle somme parziali. Quindi, per trovare il sottoarray contiguo il cui valore assoluto è minimo, suggerisco di ordinare le somme parziali e quindi di trovare i due valori più vicini, e di usare le posizioni di queste due somme parziali nella sequenza originale per trovare l'inizio e la fine della sottoschiera con il valore assoluto più piccolo.

Il bit costoso qui è il tipo, quindi penso che questo funziona nel tempo O(n * log(n)).

+1

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

+0

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

+0

Considera 3,3,3,4,5? Forse sono confuso. – Catalyst

2

La risposta è sì, l'algoritmo di Kadane è sicuramente il modo migliore per risolvere il problema.

http://en.wikipedia.org/wiki/Maximum_subarray_problem

Fonte - Ho strettamente lavorato con uno studente di dottorato che è tutta la tesi di dottorato è stata dedicata al problema massima sottoarray.

6

Stavo facendo questo test su Codility e ho trovato la risposta mcdowella abbastanza utile, ma non abbastanza ho da dire: quindi ecco una risposta 2015 ragazzi!

Abbiamo bisogno di costruire il prefisso somme dell'array A (chiamato P qui) come: P [0] = 0, P [1] = P [0] + A [0], P [2] = P [ 1] + A [1], ..., P [N] = P [N-1] + A [N-1]

La "somma minima abs" di A sarà la differenza assoluta minima tra 2 elementi in P. Quindi dobbiamo solo .sort() P e fare un ciclo attraverso di esso prendendo ogni volta 2 elementi successivi. In questo modo abbiamo O (N + N log (N) + N) che è uguale a O (N log (N)).

Questo è tutto!

+0

Sono curioso di vedere come l'hai implementato. – Maresh

+0

L'ho implementato in Python ma non ho più il codice ... Qual è la parte che ti interessa di più? Posso spiegare di più. – Saksow

+2

Che dire di questo array [-5,8, -1]? la P è [0, -5,3,2], quindi la differenza min abs tra gli elementi P è 1 (2,3), ma la somma abs minima di A è 2 (-5,8, -1). O questo: [14, -4,5] che dà P [0,12,10,15], quindi il differenziale minimo di P è 2 (10,12), ma di A è 1 (-4,5) – Benubird

0

Ecco una soluzione C basata sull'algoritmo di Kadane. Speriamo che sia utile.

#include <stdio.h> 
int min(int a, int b) 
{ 
    return (a >= b)? b: a; 
} 

int min_slice(int A[], int N) { 
if (N==0 || N>1000000) 
return 0; 

int minTillHere = A[0]; 
int minSoFar = A[0]; 
int i; 
for(i = 1; i < N; i++){ 
    minTillHere = min(A[i], minTillHere + A[i]); 
    minSoFar = min(minSoFar, minTillHere); 
    } 
return minSoFar; 
} 


int main(){ 
int A[]={3, 2, -6, 4, 0}, N = 5; 
//int A[]={3, 2, 6, 4, 0}, N = 5; 
//int A[]={-4, -8, -3, -2, -4, -10}, N = 6; 
printf("Minimum slice = %d \n", min_slice(A,N)); 
return 0; 
} 
+0

Questo non riesce ad affrontare l'assoluto – Paparazzi

0
public static int solution(int[] A) { 
    int minTillHere = A[0]; 
    int absMinTillHere = A[0]; 
    int minSoFar = A[0]; 
    int i; 
    for(i = 1; i < A.length; i++){ 
     absMinTillHere = Math.min(Math.abs(A[i]),Math.abs(minTillHere + A[i])); 
     minTillHere = Math.min(A[i], minTillHere + A[i]); 
     minSoFar = Math.min(Math.abs(minSoFar), absMinTillHere); 
     } 
    return minSoFar; 
} 
3

Questo è C++ implementazione dell'algoritmo di Saksow.

int solution(vector<int> &A) { 
    vector<int> P; 
    int min = 20000 ; 
    int dif = 0 ; 
    P.resize(A.size()+1); 
    P[0] = 0; 
    for(int i = 1 ; i < P.size(); i ++) 
    { 
     P[i] = P[i-1]+A[i-1]; 

    } 
    sort(P.begin(),P.end()); 
    for(int i = 1 ; i < P.size(); i++) 
    { 
     dif = P[i]-P[i-1]; 
     if(dif<min) 
     { 
      min = dif; 
     } 
    } 
    return min; 
} 
0
def min_abs_subarray(a): 
    s = [a[0]] 
    for e in a[1:]: 
     s.append(s[-1] + e) 
    s = sorted(s) 
    min = abs(s[0]) 
    t = s[0] 
    for x in s[1:]: 
     cur = abs(x) 
     min = cur if cur < min else min 
     cur = abs(t-x) 
     min = cur if cur < min else min 
     t = x 
    return min 
-1

Puoi corsaKadane's algorithmdue volte (o di farlo in una volta sola) per trovare importo minimo e massimo in cui trovare opere minime stesso modo di massima con invertito segni e quindi calcolare nuovo massimo confrontando il loro valore assoluto.

Fonte: Qualcuno (non ricordo chi) commenta questo sito.

Problemi correlati