How to find the Largest Difference in an Array

Question

Suppose I have an array of integers:

int[] A = { 10, 3, 6, 8, 9, 4, 3 };

My goal is to find the largest difference between A[Q] and A[P] such that Q > P.

For example, if P = 2 and Q = 3, then

diff = A[Q] - A[P]
diff = 8 - 6
diff = 2

If P = 1 and Q = 4

diff = A[Q] - A[P]
diff = 9 - 3
diff = 6

Since 6 is the largest number between all the difference, that is the answer.

My solution is as follows (in C#) but it is inefficient.

public int solution(int[] A) {

    int N = A.Length;
    if (N < 1) return 0;

    int difference;
    int largest = 0;

    for (int p = 0; p < N; p++)
    {
        for (int q = p + 1; q < N; q++)
        {
            difference = A[q] - A[p];
            if (difference > largest)
            {
                largest = difference;
            }
        }
    }

    return largest;
}

How can I improve this so it will run at O(N)? Thanks!

Simply getting the max and min wont work. Minuend (Q) should come after the Subtrahend (P).

This question is based on the "Max-profit" problem in codility (http://codility.com/train/). My solution only scored 66%. It requires O(N) for a score of 100%.

Answer 1

Here is the O(n) Java implementation

public static int largestDifference(int[] data) {
    int minElement=data[0], maxDifference=0;

    for (int i = 1; i < data.length; i++) {
        minElement = Math.min(minElement, data[i]);
        maxDifference = Math.max(maxDifference, data[i] - minElement);
    }
    return maxDifference;
}

Answer 2

The following code runs in O(n) and should conform to the specification (preliminary tests on codility were successful):

public int solution(int[] A)
{
    int N = A.Length;
    if (N < 1) return 0;

    int max = 0;
    int result = 0;

    for(int i = N-1; i >= 0; --i)
    {
        if(A[i] > max)
            max = A[i];

        var tmpResult = max - A[i];        
        if(tmpResult > result)
            result = tmpResult;
    }

    return result;
}

Update:
I submitted it as solution and it scores 100%.

Update 02/26/16:
The original task description on codility stated that "each element of array A is an integer within the range [0..1,000,000,000]."
If negative values would have been allowed as well, the code above wouldn't return the correct value. This could be fixed easily by changing the declaration of max to int max = int.MinValue;