Find the maximum amount in an array

Question

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

Consider an array

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

I need to find the maximum difference between two elements at positions i and j such that i < j , that is, I want to find the maximum difference between two elements, where the second element comes after the 1st element.

At the input, I gave the answer 7 , because 8-1 = 7 and 8 after 1 .

The program works, but when I have a very large array, it takes a lot of time. Can we improve 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 to everyone for the answers. I used code using codeaddict and it works fast.

Answer 1

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

You compare each element with any other element. Instead, you can track the maximum difference and the minimum element that is still visible.

So, every time you check a new item, you see

• if its difference with the current min gives the best maximum amount, if so, update the maximum amount and
• if this number is less than the minimum while you update 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; } 

Perfect link

Answer 2

One iteration, minimum tracking and maxdiff. In each element, if the value is less than the minimum, set the minimum value; otherwise, if the value is a minimum greater than maxdiff, set maxdiff to this difference. Derives it from O (n ^ 2) to O (n).

Answer 3

That should work. I have not tested it.

 $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";