如何找到最大的不同在数组中 [英] How to find the Largest Difference in an Array

问题描述

假设我有一个整数数组：

Suppose I have an array of integers:

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

我的目标是要找到之间的[Q]和最大的差别A [P]，使得Q> P中。

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

例如，若P = 2且Q = 3，然后

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

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

如果P = 1和Q = 4

If P = 1 and Q = 4

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

由于图6是所有的差异之间的最大数目，即答案。

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

我的解决方法如下（在C＃），但它是低效的。

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

我怎样才能改善这种因此它会在O（N）上运行？谢谢！

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

仅仅让MAX和MIN不会工作。被减数（Q）应该减数（P）之后。

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

这个问题是基于codility最大利润的问题（ http://codility.com/train/ ）。我的解决方案只打进了66％。它需要O（N）的100％的高分。

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

推荐答案

以下code运行在O（n）和应的符合规范（上codility preliminary测试成功）：

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

更新：
我提出它作为解决方案，它的分数为100％。

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

这篇关于如何找到最大的不同在数组中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！