find max sum in array

Question

I have a working solution for my problem but now I want to improve it.

Consider the array

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

I need to find the max difference between two elements at position i and j such that i < j that is I want to find max difference between two elements where the 2nd element comes after 1st element.

In the input I gave the answer is 7 because 8-1 = 7 and 8 is after 1.

The program works but when I have a very large array it takes lot of time. Can we improve on it?

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

Thanks a lot to all the answers. I have used the code by codeaddict and it works fast.

Answer 1

Your current approach is O(N^2) you can improve it to O(N).

You are comparing each element with every other element. Instead you can keep track of the max difference and min element seen so far.

So every time you test a new element you see

• if its difference with the current min will give a better max sum if so update the max sum and
• if that number is less than the min so far you update the min.

PHP function:

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

One iteration, track the minimum and the maxdiff. At each element, if the value is less than the minimum, set the minimum to the value; else, if the value - minimum is greater than maxdiff, set the maxdiff to that difference. Turns it from an O(n^2) to O(n).