11

整数の配列があるとします。

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

私の目標は、Q > P となる A[Q] と A[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% しかありませんでした。100% のスコアには O(N) が必要です。

4

11 に答える 11

20

次のコードは 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% です。

2016 年 2 月 26 日の更新: codility
に関する元のタスクの説明では、「配列 A の各要素は [0..1,000,000,000] の範囲内の整数である」と述べられていました。
負の値も許可されていた場合、上記のコードは正しい値を返しません。maxこれは、宣言をto に変更することで簡単に修正できます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

100/100 を与える codility テスト タスクの MaxProfit の C++ ソリューション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

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 に答える
-1

http://www.rationalplanet.com/php-related/maxprofit-demo-task-at-codility-com.htmlにある 100/100 を与える codility テスト タスクの MaxProfit の PHP ソリューション

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

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 に答える
-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

より洗練された機能的アプローチを使用した Javascript ソリューションの 100%。

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 に答える