Find Maximum Difference Between Two Elements in Java
Problem
The maximum difference is the largest result of subtracting some earlier element from some later element — equivalent to buying at the lowest price seen so far and selling at the best later price.
Given an array of integers, find the maximum value of arr[j] - arr[i] for any pair where j comes after i.
Java Program
public class MaxDifference {
public static void main(String[] args) {
int[] arr = {7, 1, 5, 3, 6, 4};
int maxDiff = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) { // j always comes after i
if (arr[j] - arr[i] > maxDiff) {
maxDiff = arr[j] - arr[i];
}
}
}
System.out.println("Maximum difference: " + maxDiff);
}
}Output
Core Logic
Trying every pair of positions where the second comes after the first, and keeping the best difference found, checks every valid pairing directly.
- 1The outer loop picks an earlier index
i, and the inner loop picks a later indexj, always starting fromi + 1. - 2For each pair,
arr[j] - arr[i]is computed — a later value minus an earlier one, never the reverse. - 3Whenever that difference beats
maxDiff,maxDiffis updated to it. - 4After every pair has been checked,
maxDiffholds the largest achievable difference.
[7, 1, 5, 3, 6, 4], the pair (index 1 = 1, index 4 = 6) gives 6 - 1 = 5, the largest difference found across every pair.Key Point: The inner loop always starts at i + 1, not 0 — this is what enforces 'later minus earlier' instead of considering every possible pair regardless of order.
Why: Every pair of positions is checked explicitly, so the number of comparisons grows with the square of the array's length.
Key Concepts
Approach 2: Optimized (Single Pass)
public class MaxDifferenceOptimized {
public static void main(String[] args) {
int[] arr = {7, 1, 5, 3, 6, 4};
int minSoFar = arr[0];
int maxDiff = Integer.MIN_VALUE;
for (int i = 1; i < arr.length; i++) {
maxDiff = Math.max(maxDiff, arr[i] - minSoFar); // best sell price against the cheapest buy so far
minSoFar = Math.min(minSoFar, arr[i]); // update after, so arr[i] never compares against itself
}
System.out.println("Maximum difference: " + maxDiff);
}
}
Output
Core Logic
Tracking the smallest value seen so far while scanning left to right means every later element only needs one comparison against that running minimum, not against every earlier element individually.
- 1
minSoFarstarts atarr[0], the only candidate 'earlier' value available before the scan begins. - 2At each subsequent index,
arr[i] - minSoFargives the best difference achievable by selling at this position. - 3
Math.max(maxDiff, ...)keeps the best difference seen across all positions checked so far. - 4
Math.min(minSoFar, arr[i])updates the running minimum afterward, so it's always the smallest value from everything scanned before the current position.
[7, 1, 5, 3, 6, 4], minSoFar drops to 1 at index 1, and every later difference is measured against that 1 — including 6 - 1 = 5, the eventual answer.Key Point: Updating minSoFar after computing the difference — not before — is what keeps 'later minus earlier' true; updating it first would let an element be compared against itself.
Why: A single pass keeps just two running values — the best difference and the smallest value seen so far — instead of comparing every pair explicitly.