Dato un array non trovato trova il valore massimo di A [j] - A [i] dove j> i..in O (n) tempo

Question

Questa è una domanda di intervista Amazon.Io ho risolto questo problema in O (n) usando dinamica programming.But voglio sapere ci può essere più di ottimizzazione di O (n)

per esempio supponiamo che segue è la matrice

3 7 1 4 2 4 returns 4 

5 4 3 2 1 returns Nothing 

4 3 2 2 3 returns 1 

Questo è il codice che ho scritto Code

Answer 1

Diciamo che hai int A[N].

int res = -1; 
int min_value = A[0]; 
for(int i=1; i<N; i++) { 
    // A[i] - A[j] is maximal, when A[j] is minimal value from {A[0], A[1],.., A[i-1]} 
    res = max(res, A[i] - min_value); 
    min_value = min(min_value, A[i]); 
} 
return res; 

Complessità O (N).

È necessario esaminare N elementi in modo che O (N) sia il migliore possibile.

Answer 2

ma voglio sapere ci può essere più di ottimizzazione poi O (n)

qualsiasi dei n elementi possono essere parte della soluzione, e quindi ogni deve essere esaminato. Pertanto, non è possibile migliorare O(n).

Per completezza, ecco una soluzione che richiede tempo e richiede O(n)O(1) memoria:

A = [1, 10, 20, -10, 3, 4, 18, 42, 15] 

smallest = A[0] 
maxdiff = float('-inf') 
for x in A[1:]: 
    maxdiff = max(maxdiff, x - smallest) 
    smallest = min(smallest, x) 
print maxdiff 

Answer 3

Non può essere fatto meglio di O (n), perché qualunque sia l'approccio utilizzato, si dovrà iterare sopra l'array almeno una volta e quel passo in sé è O (n). Riposa il combattimento rimane solo per ridurre al minimo le costanti.

Answer 4

public static int maxOrderedDiff(int[] A){ 
    //A[x]-A[y] | x>y 
    int min = 0, max = 0; 
    int less = 0; 
    for(int i=1; i<A.length; i++){ 
     if(A[less]>A[i]){ 
      less = i; 
     } 
     if(A[i]-A[min]>A[max]-A[min] || A[i]-A[less] >A[max]-A[min]){ 
      max=i; 
      if(A[less]<A[min]) 
       min = less; 
     } 
    } 

    return max>min? A[max]-A[min]: -1; 
}//maxOrderedDiff 

TEST CON:

public static void main(String[] args){ 
    int[][] A = {{3, 7, 1, 4, 2, 4},{5, 4, 3, 2,1},{4, 3, 2, 2, 3}}; 

    for(int[] B: A) 
     System.out.format("%s :: %d%n", Arrays.toString(B), maxOrderedDiff(B)); 
}