найти максимальную сумму в массиве

Question

У меня есть рабочее решение для моей проблемы, но теперь я хочу улучшить его.

Рассмотрим массив

3,4,5,9,1,2,8

Мне нужно найти максимальную разницу между двумя элементами в положении i и j так, что i < j, то есть я хочу найти максимальную разницу между двумя элементами, где 2-й элемент идет после 1-го элемента.

На входе, который я дал, ответ 7, потому что 8-1 = 7 и 8 после 1.

Программа работает, но когда у меня очень большой массив, это занимает много времени.Можем ли мы улучшить это?

function fMax($arr) 
{
        $sum = $arr[1] - $arr[0];

        for($i=0;$i<count($arr);$i++) 
        {
                for($j=$i+1;$j<count($arr);$j++) 
                {
                        if($sum < $arr[$j] - $arr[$i]) 
                        {
                                $sum = $arr[$j] - $arr[$i];
                        }
                }
        }
        return $sum;
}

Большое спасибо за все ответы.Я использовал код по codeaddict, и он работает быстро.

Answer 1

Ваш текущий подход O(N^2), вы можете улучшить его до O(N).

Вы сравниваете каждый элемент с каждым другим элементом.Вместо этого вы можете отслеживать максимальную разницу и минимальный элемент, видимый до сих пор.

Так что каждый раз, когда вы тестируете новый элемент, вы видите

• , если его разница с текущим минимумом дастЛучшая максимальная сумма, если это так, обновите максимальную сумму и
• , если это число меньше минимального, пока вы обновляете минимальную

функцию PHP:

function ImprovedFindMax($arr) {
    // initial max sum.
    $sum = $arr[1] - $arr[0];

    // initial min.
    $min = $arr[0];

    // iterate for every other ele starting from 2nd.
    for($i=1;$i<count($arr);$i++) {
            // if this ele give larger sum then update sum.
        if($arr[$i] - $min > $sum) {
            $sum = $arr[$i] - $min;
        }

            // if this ele is smaller than min..update min.
        if($arr[$i] < $min) {
            $min = $arr[$i];
        }
    }

    // return $sum which will be the max sum.
    return $sum;
}

Ideone Link

Answer 2

Одна итерация, отслеживание минимального и максимального значения.В каждом элементе, если значение меньше минимального, установите минимальное значение;иначе, если значение - минимум больше, чем maxdiff, установите maxdiff на эту разницу.Превращает его из O (n ^ 2) в O (n).

Answer 3

Это должно работать. Я не проверял это.

$arr = array(3,4,5,9,1,2,8);

$min = PHP_INT_MAX;
$maxdiff = 0;

foreach($arr as $i) {
  if ($i < $min) {
    $min = $i;
  }

  if ($maxdiff < $i - $min) {
    $maxdiff = $i - $min;
  }
}

echo "maxdiff: {$maxdiff}\n";