CODEWITHSUNDEEP
c#algorithmpuzzle
Randal Cunanan
Randal Cunanan

Reputation: 2529

How to find the Largest Difference in an Array

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%.

Upvotes: 11

Views: 28813

Answers (13)

Muhammed kerim
Muhammed kerim

Reputation: 31

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

Upvotes: 0

noviewpoint
noviewpoint

Reputation: 584

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;

}

Upvotes: 0

Олег Трофимов
Олег Трофимов

Reputation: 11

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

Upvotes: 0

Satish
Satish

Reputation: 173

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: enter image description here

#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.

enter image description here

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

Upvotes: 0

afrizaliman
afrizaliman

Reputation: 1

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

Upvotes: 0

stukennedy
stukennedy

Reputation: 1108

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
}

Upvotes: -1

Daniel Hilgarth
Daniel Hilgarth

Reputation: 174309

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;

Upvotes: 20

craftsmannadeem
craftsmannadeem

Reputation: 2943

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

Upvotes: 4

user3403187
user3403187

Reputation: 129

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

Upvotes: -1

Jung Oh
Jung Oh

Reputation: 29

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

Upvotes: -1

Oleksandr M.
Oleksandr M.

Reputation: 673

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

Upvotes: -1

user2831284
user2831284

Reputation: 1

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

Upvotes: 0

King King
King King

Reputation: 63327

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!

Upvotes: 1

Related Questions