# Find maximum difference between values in an array

My task is to use the following pseudocode and improve it (make it run faster). Also I have to analyze the runtime of the given pseudocode and of my new code that i improved.

What does this algorithm do? It finds the smallest and greatest number in an array and creates the difference of them.

Input: Array Y, length n with n >= 2
Output: x (number)
x = 0
for i = 0 to n do
for j = i + 1 to n do
if x < A[i] - A[j] then
x = A[i] - A[j];
end if
end for
end for
return x;


My code, improved:

public class Improved
{
public static void main (String[] args)
{
int A[] = {1, 2, 3, 4, 5};
int min = A;
int max = A;

for (int i = 0; i < A.length; i++)
{
if (min > A[i])
{
min = A[i];
}

if (max < A[i])
{
max = A[i];
}
}
System.out.println(max - min);
}
}


The only problem I got now is counting the runtime. I think for the pseudocode, it runs in $\mathcal{O}(n^2)$ because of the 2 for loops. Then my code will run in $\mathcal{O}(n)$, since it only has 1 for loop, right? :P What would be the worst case by the way?

• (Conventional wisdom suggests to compare pairs of array values, and only the smaller one to the min, the larger one to the max.) – greybeard Apr 30 '16 at 19:24
• Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. – Simon Forsberg Apr 30 '16 at 20:13
• And by the way, Y is also not a good variable name... – Simon Forsberg Apr 30 '16 at 20:13
• How about using Enumerable.Max(A) - Enumerable.Min(A)? – Pete Oakey Apr 30 '16 at 23:48
• I guess we should read Y as A in your pseudo code? – Édouard May 1 '16 at 1:23

What does this algorithm do? It finds the smallest and greatest number in an array and creates the difference of them.

Nope.

Consider {5, 2, 1}. The pseudo code returns 5 - 1 = 4 which happens to be the difference between the smallest and the largest value.

Now consider {1, 2, 5}. The pseudo code computes 1 - 2, 1 - 5, 2 - 5 and never updates x because all these values are < 0; the pseudo code then returns x, which is still 0. The difference between the largest and the smallest value, however, is still 5 - 1 = 4.

### Code review

As others have pointed out, your code is not an improved version of the given pseudocode, but a different program altogether. Here's a review of your solution.

It's important to use meaningful, descriptive names for your program elements. It's impossible to guess what a class named "Improved" will do, and what a variable named "A" might be. Try to come up with better names.

Instead of putting some code in a main method, setting some hardcoded values, doing some logic and printing a result, it would be better to create a method with a single purpose, with a good name, input parameters and return value.

In the loop, you don't really need the loop index variable. In cases like this, it's strongly recommended to use an enhanced for-each loop instead.

The formatting of the code is also unusual, and doesn't follow common Java conventions.

Something like this would be better:

public class ArrayUtils {
public static int findMaxDifference(int[] arr) {
assert arr.length > 0;

int min = arr;
int max = arr;

for (int value : arr) {
if (min > value) {
min = value;
}
if (max < value) {
max = value;
}
}
return max - min;
}
}


Note that the assert keyword serves mostly as documentation, in production code it has no effect, typically only enabled during unit test runners or debuggers.

The only problem I got now is counting the runtime. I think for the pseudocode, it runs in O(n^2) because of the 2 for loops. Then my code will run in O(n), since it only has 1 for loop, right? :P What would be the worst case by the way?

Not really a good Code Review question, but I'll answer anyway. Yes, the pseudocode compares every element with every other element, and so its runtime is proportional to $N^2$, and your algorithm iterates over the elements only once, so its runtime is proportional to $N$.

The only problem I got now is counting the runtime. I think for the pseudocode, it runs in O(n^2) because of the 2 for loops.

Correct.

Then my code will run in O(n), since it only has 1 for loop, right?

Correct.

What would be the worst case by the way?

O(n) as well. Best-case, worst-case, average-case, they are all O(n) here. You are always looping through the entire list once, no matter what.

Your code looks nice, the only thing I would improve would be some one variable name: A can be named input or numbers or similar. No need to use a one-character variable name for that.

A very minor issue is that your for loop can start at 1, as you use index 0 already to initialize min and max.

The pseudocode returns the maximum difference between an array item and one of its non-strictly following values

max { Aᵢ-Aⱼ : 0 ≤ i ≤ j < n }


As Taemyr explained, your code is equivalent to the math below instead of the above one:

max { Aᵢ-Aⱼ : 0 ≤ i < n, 0 ≤ j < n } = max { Aᵢ : 0 ≤ i < n } - min { Aᵢ : 0 ≤ i < n }


The first problem can also be computed in O(n) time.

max { Aᵢ-mᵢ : 0 ≤ i < n-1 }, mᵢ = min { Aⱼ : i ≤ j < n }

maxDiff = 0;
minNum = A[n-1];
for i=n-2 to 0
if A[i]-minNum > maxDiff then
maxDiff = A[i]-minNum;
else if A[i] < minNum then
minNum = A[i];
end if
end for
return maxDiff;


Or iterating forwards,

max { Mᵢ-Aᵢ : 1 ≤ i < n }, Mᵢ = max { Aⱼ : 0 ≤ j ≤ i }

maxDiff = 0;
maxNum = A;
for i=1 to n-1
if maxNum-A[i] > maxDiff then
maxDiff = maxNum-A[i];
else if A[i] > maxNum then
maxNum = A[i];
end if
end for
return maxDiff;


A really good habit to have is to separate out the different "concerns" in to separate functions. your main method does 3 things:

1. build a test dataset
2. compute the largest difference
3. print the result.

This leads to a main method which should look like:

public static void main (String[] args) {
int[] data = testData();
int maxDiff = maximumDifference(data);
System.out.println(maxDiff);
}


The testData method would be easy to implement.

The maximumDifference method can have the single concern now of the basic computation. Note that Java8 has some nice streaming tricks:

public static int maximumDifference(int[] data) {
IntSummaryStatistics stats = IntStream.of(data).summaryStatistics();
if (stats.getCount() == 0) {
return 0;
}
return stats.getMax() - stats.getMin();
}


There are some issues you may run in to. If someone puts values in tot he array that together exceed the Integer.MAX_VALUE limit, then the result will be wrong. It would be more correct to return a long value from the method, and convert the Min and Max values to longs before computing the diff. For example, what is the maximumDifference(...) in [2147483647, -100]

1

It would be nice to put the actual difference computing routine in its own method.

2

You can do a minor optimization. Instead of

if (min > A[i])
{
min = A[i];
}

if (max < A[i])
{
max = A[i];
}


you could write

if (min > A[i]) {
min = A[i];
} else if (max < A[i]) {
max = A[i];
}


since any element - except the first one - cannot be both a new maximum and a new minimum, we don't need to check the second condition above in case the first one passed.

3

The general Java coding conventions dictate that the opening brace is on the same line with the token it relates to, separated by a single space. So instead of

if (funky())
{
yeah();
}


you should write

if (funky()) {
yeah();
}


4

You should validate the input against being a null or an empty array, and throw an appropriate exception, in case something's fishy.

Summa summarum

Putting all points together, I had this in mind:

public class Main {

public static int difference(final int... array) {
if (array.length == 0) {
throw new IllegalArgumentException("The input array is empty.");
}

int max = array;
int min = array;

for (final int i : array) {
if (max < i) {
max = i;
} else if (min > i) {
min = i;
}
}

return max - min;
}

public static void main(final String[] args) {
System.out.println(difference(1, 2, 3, 4, 5));
}
}


Hope that helps.