如何找到数组中最大的差异

Question

假设我有一个整数数组:

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

我的目标是找到A [Q]和A [P]之间的最大差异,使得Q> P.

例如,如果P = 2且Q = 3,那么

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

如果P = 1且Q = 4

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

由于6是所有差异之间的最大数字,这就是答案.

我的解决方案如下(在C#中),但效率很低.

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

我怎样才能改进这个以便它在O(N)运行？谢谢!

简单地让最大和最小不会工作.Minuend(Q)应该在Subtrahend(P)之后.

这个问题是基于鳕鱼的"最大利润"问题(http://codility.com/train/).我的解决方案只得到了66%.它需要O(N)得分为100%.

Answer 1

以下代码在O(n)中运行,并且应符合规范(成功的初步测试成功):

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

更新:
我提交了它作为解决方案,它得分为100%.

更新02/26/16:
关于codility的原始任务描述表明"数组A的每个元素都是[0..1,000,000,000]范围内的整数."
如果也允许负值,则上面的代码不会返回正确的值.这可以通过更改maxto 的声明轻松修复int max = int.MinValue;