algoritmo per trovare il più grande calo in un array

Question

Ho una domanda algoritmo:

Dato un array (assumendo tutti gli elementi sono intergers) di dimensione N, troviamo il più grande calo (non necessariamente continuo): max {array [i] -array [j]} con un vincolo: i> j.

La soluzione semplice è che due cicli passano attraverso tutti i possibili valori di i e j, ma la complessità temporale è O (n * n).

E una soluzione migliore penso sia quella di mappare prima gli indici dell'array, ordinare l'array e passare attraverso l'array per trovare la goccia più grande. Questa complessità è O (nlogn).

Esiste una soluzione con complessità temporale lineare? E come?

PS: Una volta ho pensato a una soluzione lineare: creare due array aggiuntivi, uno è registrare il valore massimo dell'array dato dall'inizio alla fine e l'altro al valore minimo dalla fine all'inizio. Quindi, passare attraverso due array di un passaggio. Tuttavia, qualcuno ha pensato che non correttamente e occupando troppo spazio. Quindi voglio sapere una soluzione migliore. - lijuanliu

Answer 1

Creare nuovi 2 campi:

max[i] = max { arr[0], arr[1], ..., arr[i] } 
min[i] = min { arr[n-1], arr[n-2], ..., arr[i] } 
(max is the maximum from first to i, min is the minimum from i to last) 

Ora, scorrere gli array AUSILIARI e trovare il differenza massima max[i] - min[i]

Ciò richiede 3 iterazioni complessive ed è quindi O(n).

prova di correttezza (linee guida):

Facciamo il più grande calo sia dall'indice i all'indice j, dove i<j:

1. Poi, max[i] >= arr[j] (perché abbiamo già passato), e anche min[i] <= arr[i] - quindi max[j] - min[j] >= arr[i] - arr[j] e la risposta fornita dall'algoritmo è almeno altrettanto valida della ottimale.
2. Inoltre, dal momento che il calo più sensibile è i,j, non vi sarà alcun k<j tale che arr[k] < arr[i], perché poi il calo più sensibile sarà arr[k]-arr[j].Analogamente - non ci può essere k>j tale che arr[k] < arr[j], per le stesse ragioni - e quindi max[j]-min[j] <= arr[i] - arr[j]

Da quanto sopra si può concludere che max[j]-min[j] = arr[i] - arr[j]. Tutto è lasciato per una dimostrazione completa formale è dimostrare che per ogni k si ottiene max[k]-min[k] <= max[j] - min[j], e questo è davvero il caso, altrimenti ci sono alcuni u<k, v>k tale che max[k]=arr[u], min[k]=arr[v], e si ottiene che arr[u] - arr[v] > arr[i] - arr[j], che contraddice il fatto che i,j è il goccia più grande.

QED

Answer 2

Posso solo pensare a O (nlogn) ma questo anche se la stessa complessità dovrebbe essere più veloce di ordinare e trovare la goccia più grande.

Che cosa si può fare è quello di calcolare le differenze dei numeri consecutivi in ​​O (n), e quindi il problema si ridurrebbe a trovare il MAX (somma) di sub-array continua che sarebbe O (nlogn)

Answer 3

È necessario tenere traccia di due cose:

Il numero massimo visualizzato fino all'elemento i e il calo più grande che si è riscontrato rispetto al numero più grande (ovvero il numero massimo prima di I, meno l'elemento i). Questo sarà O (n) nel tempo e O (1) nello spazio.

Questo problema è esattamente il "magazzino di acquisto/vendita" questione intervista, una soluzione può essere trovata qui: Maximum single-sell profit

Answer 4

public static int maxDrop(int[]array){ 

    int maxDrop =0,drop=0,min=array[0]; 

    for(int i=1;i<array.length;i++){ 

     if(array[i]<min){ 
      min=array[i]; 
     } 

     drop = array[i]-min; 

     if(drop>maxDrop){ 
      maxDrop=drop; 
     } 

    } 

    System.out.println(maxDrop); 
    return maxDrop; 

} 

Answer 5

O (n) soluzione senza spazio extra:

public int maxDrop(int[] a) { 
    int max = a[0]; 
    int maxDrop = -1; 
    for (int i = 0; i < a.length; i++) { 
     if (max < a[i]) { 
      max = a[i]; 
     } 
     else { 
      int drop = max - a[i]; 
      maxDrop = Math.max(maxDrop, drop); 
     } 
    } 
    return maxDrop; 
}