Question:

You 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.

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.

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

Solution:

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;
}
Reactions:

Post a Comment Disqus

 
Top