Cho một Array chưa phân loại tìm giá trị lớn nhất của A [j] - A [i] trong đó j> i..in O (n) time

Question

Đây là một cuộc phỏng vấn của Amazon Question.I đã giải quyết vấn đề này trong O (n) bằng cách sử dụng năng động lập trình.Nhưng tôi muốn biết có thể tối ưu hóa nhiều hơn O (n)

cho ví dụ giả sử bên dưới là mảng

3 7 1 4 2 4 returns 4 

5 4 3 2 1 returns Nothing 

4 3 2 2 3 returns 1 

Đây là mã tôi đã viết Code

Answer 1

Cho phép nói rằng bạn đã có 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; 

Độ phức tạp O (N).

Bạn cần kiểm tra các phần tử N để O (N) là tốt nhất những gì bạn có thể nhận được.

Answer 2

Nhưng tôi muốn biết có thể có nhiều hơn tối ưu hóa sau đó O (n)

Bất kỳ của n yếu tố có thể là một phần của giải pháp, và do đó mỗi cần phải được kiểm tra. Do đó, không thể cải thiện O(n).

Để hoàn chỉnh, đây là một giải pháp mà mất O(n) thời gian và đòi hỏi O(1) bộ nhớ:

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

Nó không thể được thực hiện tốt hơn so với O (n) vì bất cứ điều gì phương pháp bạn sử dụng, bạn sẽ phải lặp trên mảng ít nhất một lần và bước đó là O (n). Phần còn lại cuộc chiến vẫn chỉ để giảm thiểu các hằng số.

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 

thử nghiệm với:

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