Ответ 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:
В исходном описании задачи о кодовости указано, что "каждый элемент массива A является целым числом в пределах диапазона [0,1,000,000,000]".
Если бы отрицательные значения были бы допущены, код выше не вернул бы правильное значение. Это можно легко устранить, изменив объявление max на int max = int.MinValue;

Ответ 2

Здесь реализована реализация 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;
}

Ответ 3

После некоторых попыток я получаю следующее:

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;

ПРИМЕЧАНИЕ. Я только что протестировал его в некоторых случаях. Если вы найдете какой-либо случай, в котором он не работает, сообщите мне в комментарии. Я постараюсь улучшить его или удалить ответ. Спасибо!

Ответ 4

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

Ответ 5

PHP-решение для MaxProfit задачи проверки кодовости, дающее 100/100, найденное в http://www.rationalplanet.com/php-related/maxprofit-demo-task-at-codility-com.html

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

Ответ 6

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

Ответ 7

Решение 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

Ответ 8

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
}