1. Introduction
Finding the maximum difference between two elements in an array helps in optimization, decision-making, and analysis. For example, a stock market application can use it to calculate profit from buying low and selling high. In this example, I will show several ways to find the maximum difference between any two elements in an integer array:
- Find the maximum difference between all pairs of elements using nested loops. This approach has a time complexity of
O(n^2). - The maximum difference is the difference between the smallest and largest values. I will show three ways to find the smallest and largest values. This approach has a time complexity of
O(n).
2. Setup
In this step, I will create a Java project in Eclipse with the Junit 5 library.
3. Elements Max Difference Array Class
In this step, I will create a FindElements.java class that has four methods to find the maximum difference between any two elements from an integer array.
findMaxDiffViaMathMinMaxValues– find the maximum difference by calculating the difference between the smallest and largest values. It utilizes thejava.lang.Math.maxandjava.lang.Math.minfunctions.findMaxDiffViaMinMaxValues– find the maximum difference by calculating the difference between the smallest and largest values.findMaxDiffViaNestedLoop– find the maximum difference between all pairs of elements via a nested loop. This method has a time complexity ofO(n^2), which can be inefficient for large arrays.findMaxDiffViaTreeSet– find the maximum difference by calculating the difference between the smallest and largest values. It utilizesjava.util.TreeSetdata structure because A TreeSet automatically keeps elements in sorted order.
FindElements.java
package org.zheng.demo;
import java.util.TreeSet;
public class FindElements {
public int findMaxDiffViaMathMinMaxValues(final int[] numbers) {
Integer maxV = Integer.MIN_VALUE;
Integer minV = Integer.MAX_VALUE;
for (Integer num : numbers) {
maxV = Math.max(maxV, num);
minV = Math.min(minV, num);
}
return maxV - minV;
}
public int findMaxDiffViaMinMaxValues(final int[] numbers) {
Integer maxV = Integer.MIN_VALUE;
Integer minV = Integer.MAX_VALUE;
for (Integer num : numbers) {
if (num > maxV) {
maxV = num;
}
if (num < minV) {
minV = num;
}
}
return maxV - minV;
}
public int findMaxDiffViaNestedLoop(final int[] numbers) {
int maxDiff = Integer.MIN_VALUE;
for (int i = 0; i < numbers.length; i++) {
for (int j = i + 1; j < numbers.length; j++) {
int diff = Math.abs(numbers[i] - numbers[j]);
if (diff > maxDiff) {
maxDiff = diff;
}
}
}
return maxDiff;
}
public int findMaxDiffViaTreeSet(final int[] numbers) {
TreeSet<Integer> set = new TreeSet<>();
for (int num : numbers) {
set.add(num);
}
return set.last() - set.first();
}
}
- Line 11, 12: Use
Math.maxandMath.minfunctions to find the bigger and smaller values. - Line 21, 25: Use
>and<to find the bigger and smaller values. - Line 38, 39: Calculate the difference with
Math.absfunction and compare each difference to find the maximum difference. - Line 51, 54: Use a
TreeSetto calculate the maximum difference between the first and last elements asTreeSetis sorted automatically.
4. Test Elements Max Difference Array Class
In this step, I will create a FindElementsTest.java test class to verify the four methods created in step 3 to find the maximum difference in an integer array. The integer array contains ten random integers ranging from -10 to 10.
FindElementsTest.java
package org.zheng.demo;
import java.util.Random;
import org.junit.jupiter.api.BeforeAll;
import org.junit.jupiter.api.Test;
class FindElementsTest {
private FindElements testClass = new FindElements();
private static int[] randomArray;
@BeforeAll
static void setup() {
randomArray = new Random().ints(10, -10, 10).toArray();
System.out.println("Integer Array elements: ");
for (int num : randomArray) {
System.out.print(num + ", ");
}
System.out.println("");
}
@Test
void test_findMaxDifferenceViaMinMaxValues() {
Integer maxDiff = testClass.findMaxDiffViaMinMaxValues(randomArray);
System.out.println("findMaxDiffViaMinMaxValues returns the maximum difference: " + maxDiff);
}
@Test
void test_findMaxDifferenceViaMathMinMaxValues() {
Integer maxDiff = testClass.findMaxDiffViaMathMinMaxValues(randomArray);
System.out.println("findMaxDiffViaMathMinMaxValues returns the maximum difference: " + maxDiff);
}
@Test
void test_findMaxDiffViaNestedLoop() {
int maxDiff = testClass.findMaxDiffViaNestedLoop(randomArray);
System.out.println("findMaxDiffViaNestedLoop returns the maximum difference: " + maxDiff);
}
@Test
void test_findMaxDiffViaTreeSet() {
int maxDiff = testClass.findMaxDiffViaTreeSet(randomArray);
System.out.println("findMaxDiffViaTreeSet returns the maximum difference: " + maxDiff);
}
}
5. Demo
In this step, I will run the tests and capture the results.
Figure 2 shows an integer array with 10 elements: -6, -7, -6, 4, -8, 3, -8, -9, 9, 2. The largest number is 9 and the smallest number is -9, so the maximum difference is 18. All four methods find the maximum difference value 18. You can try to change the testing array size to a higher number and test it again. All tests will pass and you will see that the findMaxDiffViaNestedLoop will take longer time to complete as it has a time complexity of O(n^2).
6. Conclusion
In this example, I showed four methods to find the maximum difference between any two elements in an integer array. The more optimal approach is to find the minimum and maximum values in the array and compute their difference as it reduces the time complexity to O(n).
7. Download
This was an example of a Java project that included a class to find the maximum difference between any two elements from an integer array.
You can download the full source code of this example here: Finding Maximum Difference Between Array Elements Example
