Biorąc pod uwagę nieposortowaną tablicę znajdź maksymalną wartość A [j] - A [i] gdzie j> i..in O (n) czas

Question

To jest wywiad z Amazon Pytanie. Rozwiązałem ten problem w O (n) przy użyciu dynamiczne programowanie .Ale chcę wiedzieć, czy może być więcej optymalizacji niż O (n)

dla np. załóżmy poniżej jest tablica

3 7 1 4 2 4 returns 4 

5 4 3 2 1 returns Nothing 

4 3 2 2 3 returns 1 

Jest to kod Pisałem Code

Answer 1

Powiedzmy masz 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; 

Złożoność O (N).

Musisz sprawdzić N elementów, więc O (N) jest najlepsze, co możesz dostać.

Answer 2

Ale chcę wiedzieć, może istnieć więcej optymalizacja następnie O (n)

Każda z n elementów może być częścią rozwiązania, a zatem każdy musi zostać zbadane. Tak więc, O(n) nie może zostać ulepszone.

Dla kompletności, tutaj jest to rozwiązanie, które zajmuje czas i wymaga O(n)O(1) Pamięć:

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

Nie można zrobić lepiej niż O (n), ponieważ cokolwiek podejście użyć, trzeba będzie iteracyjne po tablicy co najmniej raz i ten krok sam w sobie jest O (n). Reszta walka pozostaje tylko do zminimalizowania stałych.

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 Z:

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)); 
}