How to find the Largest Difference in an Array

Question

Suppose I have an array of integers:

int[] A = { 10, 3, 6, 8, 9, 4, 3 };

My goal is to find the largest difference between A[Q] and A[P] such that Q > P.

For example, if P = 2 and Q = 3, then

diff = A[Q] - A[P]
diff = 8 - 6
diff = 2

If P = 1 and Q = 4

diff = A[Q] - A[P]
diff = 9 - 3
diff = 6

Since 6 is the largest number between all the difference, that is the answer.

My solution is as follows (in C#) but it is inefficient.

public int solution(int[] A) {

    int N = A.Length;
    if (N < 1) return 0;

    int difference;
    int largest = 0;

    for (int p = 0; p < N; p++)
    {
        for (int q = p + 1; q < N; q++)
        {
            difference = A[q] - A[p];
            if (difference > largest)
            {
                largest = difference;
            }
        }
    }

    return largest;
}

How can I improve this so it will run at O(N)? Thanks!

Simply getting the max and min wont work. Minuend (Q) should come after the Subtrahend (P).

This question is based on the "Max-profit" problem in codility (http://codility.com/train/). My solution only scored 66%. It requires O(N) for a score of 100%.

Answer 1

The following code runs in O(n) and should conform to the specification (preliminary tests on codility were successful):

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

Update:
I submitted it as solution and it scores 100%.

Update 02/26/16:
The original task description on codility stated that "each element of array A is an integer within the range [0..1,000,000,000]."
If negative values would have been allowed as well, the code above wouldn't return the correct value. This could be fixed easily by changing the declaration of max to int max = int.MinValue;

Answer 2

Here is the O(n) Java implementation

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

Answer 3

After some attempts, I end up with this:

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;

NOTE: I have just tested it with some cases. Please if you find any case in which it doesn't work, let me know in the comment. I'll try to improve it or remove the answer. Thanks!

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

Answer 5

PHP Solution

<?php
$a = [0,5,0,5,0];
$max_diff = -1;
$min_value = $a[0];
for($i = 0;$i<count($a)-1;$i++){
    if($a[$i+1] > $a[$i]){
        $diff = $a[$i+1] - $min_value;
        if($diff > $max_diff){
            $max_diff = $diff;
        }
    } else {
        $min_value = $a[$i+1];
    }
}
echo $max_diff;
?>

Answer 6

We can do it in a much simpler way by calculating biggest and smallest element of the array. I know that you're also looking for time complexity. But for anyone looking to understand and solve this problem in a simple and easy to understand way, then here is my code:

#include<stdio.h>  
  
#define N 6  
  
int main()  
{  
    int num[N], i, big, small, pos = 0;  
  
    printf("Enter %d integer numbers\n", N);  
    for(i = 0; i < N; i++)  
        scanf("%d", &num[i]);  
  
    big = small = num[0];  
  
    for(i = 1; i < N; i++)  
    {  
        if(num[i] > big)  
        {  
            big = num[i];  
            pos = i;  
        }  
    }  
  
    for(i = 1; i < pos; i++)  
    {  
        if(num[i] < small)  
            small = num[i];  
    }  
  
    printf("The largest difference is %d, ", (big - small));  
    printf("and its between %d and %d.\n", big, small);  
  
    return 0;  
} 

Output:

Enter 6 integer numbers

7

9

5

6

13

2

The largest difference is 8, and its between 13 and 5.

Source: C Program To Find Largest Difference Between Two Elements of Array

Answer 7

C++ solution for MaxProfit of codility test task giving 100/100 https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_profit/

int Max(vector<int> &A)
{
    if (A.size() == 1 || A.size() == 0)
        return 0;
    int min_price = A[0];
    int max_val = 0;
    for (int i = 1; i < A.size(); i++)
    {
        max_val = std::max(max_val, A[i] - min_price);
        min_price = std::min(min_price, A[i]);
    }
    return max_val;
}

Answer 8

My 100% JavaScript solution with O(N) time complexity:

function solution(A) {

    // each element of array A is an integer within the range [0..200,000]
    let min  = 200000;
    // The function should return 0 if it was impossible to gain any profit.
    let maxDiff = 0;

    for (const a of A) {
        min = Math.min(min, a);
        // find the maximum positive difference (profit) between current global minimum and current value of a
        maxDiff = Math.max(maxDiff, a - min);
    }

    return maxDiff;

}

Answer 9

function solution(A) {
  var n = A.length;
  var min = Infinity, max = -Infinity, maxNet=0;
  // find smallest and largest in the array following each other 
  for(let i = 0; i < n; i++){
      if(A[i]<min) { // if you are updating the min you cannot consider the old max
          min = A[i];
          max = -Infinity;
      } else if(A[i]> max){
          max = A[i];
      }
      if(max!=-Infinity && max-min>maxNet) maxNet = max-min;
  }
  return maxNet;
}

Answer 10

PHP solution for MaxProfit of codility test task giving 100/100 found at 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;
}

Answer 11

100% score JavaScript solution.

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

Answer 12

Python solution

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

Answer 13

100% for Javascript solution using a more elegant functional approach.

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
}