11

假设我有一个整数数组：

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)？谢谢！

简单地获得最大值和最小值是行不通的。被减数 (Q) 应该在减数 (P) 之后。

这个问题基于 codility 中的“最大利润”问题（http://codility.com/train/）。我的解决方案只得分 66%。它需要 O(N) 才能获得 100% 的分数。

4

11 回答 11

20

以下代码在 O(n) 中运行，并且应该符合规范（对 codility 的初步测试是成功的）：

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

2016 年 2 月 26 日更新：
关于 codility 的原始任务描述指出“数组 A 的每个元素都是 [0..1,000,000,000] 范围内的整数。”
如果也允许负值，则上面的代码将不会返回正确的值。这可以通过更改 to 的声明max来轻松解决int max = int.MinValue;

于 2013-09-23T10:59:14.543 回答
4

这是 O(n) Java 实现

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;
}
于 2016-02-23T17:45:54.240 回答
1

经过一些尝试，我最终得到了这个：

int iMax = N - 1;
int min = int.MaxValue, max = int.MinValue;
for (int i = 0; i < iMax; i++) {
    if (min > A[i]) min = A[i];                                     
    if (max < A[N - i - 1]){
      iMax = N - i - 1;
      max = A[iMax];
    }        
 }
 int largestDiff = max - min;

注意：我刚刚在某些情况下对其进行了测试。如果您发现它不起作用的任何情况，请在评论中告诉我。我会尝试改进它或删除答案。谢谢！

于 2013-09-23T10:18:22.163 回答
0 
  int FirstIndex = -1;
            int SecondIndex = -1;
            int diff = 0;

            for (int i = A.Length-1; i >=0; i--)
            {
                int FirstNo = A[i];
                int tempDiff = 0;
                for (int j = 0; j <i ; j++)
                {
                    int SecondNo = A[j];
                    tempDiff = FirstNo - SecondNo;
                    if (tempDiff > diff)
                    {
                        diff = tempDiff;
                        FirstIndex = i;
                        SecondIndex = j;
                    }
                }
            }

            MessageBox.Show("Diff: " + diff + "   FirstIndex: " + (FirstIndex+1) + "   SecondIndex: " + (SecondIndex+1));
于 2013-09-30T13:05:52.937 回答
0

PHP解决方案

<?php
$a = [0,5,0,5,0];
$max_diff = -1;
$min_value = $a[0];
for($i = 0;$i<count($a)-1;$i++){
    if($a[$i+1] > $a[$i]){
        $diff = $a[$i+1] - $min_value;
        if($diff > $max_diff){
            $max_diff = $diff;
        }
    } else {
        $min_value = $a[$i+1];
    }
}
echo $max_diff;
?>
于 2018-10-23T09:17:19.857 回答
0

Codility 测试任务的 MaxProfit 的 C++ 解决方案给出 100/100 https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_profit/

int Max(vector<int> &A)
{
    if (A.size() == 1 || A.size() == 0)
        return 0;
    int min_price = A[0];
    int max_val = 0;
    for (int i = 1; i < A.size(); i++)
    {
        max_val = std::max(max_val, A[i] - min_price);
        min_price = std::min(min_price, A[i]);
    }
    return max_val;
}
于 2020-12-02T23:19:14.187 回答
0

我们可以通过计算数组的最大和最小元素以更简单的方式来做到这一点。我知道您也在寻找时间复杂度。但是对于任何希望以简单易懂的方式理解和解决这个问题的人来说，这里是我的代码： 在此处输入图像描述

#include<stdio.h>  
  
#define N 6  
  
int main()  
{  
    int num[N], i, big, small, pos = 0;  
  
    printf("Enter %d integer numbers\n", N);  
    for(i = 0; i < N; i++)  
        scanf("%d", &num[i]);  
  
    big = small = num[0];  
  
    for(i = 1; i < N; i++)  
    {  
        if(num[i] > big)  
        {  
            big = num[i];  
            pos = i;  
        }  
    }  
  
    for(i = 1; i < pos; i++)  
    {  
        if(num[i] < small)  
            small = num[i];  
    }  
  
    printf("The largest difference is %d, ", (big - small));  
    printf("and its between %d and %d.\n", big, small);  
  
    return 0;  
}

输出：

输入 6 个整数

7

9

5

6

13

2

最大的差异是 8，介于 13 和 5 之间。

在此处输入图像描述

资料来源： C 程序查找数组的两个元素之间的最大差异

于 2020-09-28T21:27:21.933 回答
-1

可在http://www.rationalplanet.com/php-related/maxprofit-demo-task-at-codility-com.html找到的 MaxProfit 的 codility 测试任务的 PHP 解决方案给出 100/100

function solution($A) {
    $cnt = count($A);
    if($cnt == 1 || $cnt == 0){
        return 0;
    }

    $max_so_far = 0;
    $max_ending_here = 0;
    $min_price = $A[0];

    for($i = 1; $i < $cnt; $i++){
        $max_ending_here = max(0, $A[$i] - $min_price);
        $min_price = min($min_price, $A[$i]);
        $max_so_far = max($max_ending_here, $max_so_far);
    }

    return $max_so_far;
}
于 2014-06-06T15:01:06.153 回答
-1

100% 得分 JavaScript 解决方案。

function solution(A) {
  if (A.length < 2)
    return 0;

  // Init min price and max profit
  var minPrice = A[0];
  var maxProfit = 0;

  for (var i = 1; i < A.length; i++) {
    var profit = A[i] - minPrice;
    maxProfit = Math.max(maxProfit, profit);
    minPrice = Math.min(minPrice, A[i]);
  }
  return maxProfit;
}
于 2015-05-26T03:13:19.530 回答
-1

100% 用于 Javascript 解决方案，使用更优雅的功能方法。

function solution(A) {
    var result = A.reverse().reduce(function (prev, val) {
        var max = (val > prev.max) ? val : prev.max
        var diff = (max - val > prev.diff) ? max - val : prev.diff
        return {max: max, diff: diff}
    }, {max: 0, diff: 0})
    return result.diff
}
于 2016-05-26T13:26:36.877 回答
-1

Python解决方案

def max_diff_two(arr):
    #keep tab of current diff and min value
    min_value = arr[0]

    #begin with something
    maximum = arr[1] - arr[0]

    new_min = min_value

    for i,value in enumerate(arr):
        if i == 0:
            continue

        if value < min_value and value < new_min:
            new_min = value

        current_maximum = value - min_value
        new_maximum = value - new_min

        if new_maximum > current_maximum:
            if new_maximum > maximum:
                maximum = new_maximum
                min = new_min
        else:
            if current_maximum > maximum:
                maximum = current_maximum

    return  maximum
于 2015-08-25T02:37:17.413 回答