找到数组中的最大总和

Question

我有一个解决我的问题的工作解决方案,但现在我想改进它.

考虑数组

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

我需要找到位置上两个元素之间的最大差异i,j这样i < j我想找到第二个元素位于第一个元素之后的两个元素之间的最大差异.

在输入中我给出的答案是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).

您正在将每个元素与每个其他元素进行比较.相反,您可以跟踪到目前为止看到的最大差异和最小元素.

因此,每次测试新元素时,您都会看到

• 如果它与当前min的差异将给出更好的最大总和,如果是这样更新最大总和和
• 如果该数字小于最小值,则更新最小值.

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

一次迭代,跟踪最小值和最大值.在每个元素处,如果该值小于最小值,则将最小值设置为该值; 否则,如果值 - minimum大于maxdiff,则将maxdiff设置为该差异.将其从O(n ^ 2)变为O(n).