Introduction

The maximum-difference problem asks for the largest value of arr[j] - arr[i] with the restriction that j must be greater than i. A linear-time solution exists because you do not need to compare every pair. You only need to remember the smallest value seen so far as you scan from left to right.

The Key Observation

For each position j, the best candidate on the left is not every earlier element. It is the minimum element seen before j.

That means the algorithm can keep only two pieces of state:

• 'min_so_far: the smallest value encountered up to the current index'
• 'max_diff: the best difference seen so far'

As you scan the array, compute the profit of selling at the current element after buying at min_so_far, then update the running minimum.

A Linear-Time Implementation

Here is a clear Python version.

1def max_difference(values):
2    if len(values) < 2:
3        raise ValueError("need at least two elements")
4
5    min_so_far = values[0]
6    max_diff = values[1] - values[0]
7
8    for current in values[1:]:
9        max_diff = max(max_diff, current - min_so_far)
10        min_so_far = min(min_so_far, current)
11
12    return max_diff
13
14
15print(max_difference([2, 3, 10, 6, 4, 8, 1]))

The result is 8, produced by buying at 2 and later selling at 10.

Why This Works

Suppose you are looking at one position j. Any valid answer ending at j must subtract some earlier value arr[i] where i < j.

Among all those earlier values, the smallest one gives the biggest difference. So if you already know the smallest earlier value, you already know the best possible partner for the current element.

That removes the need for nested loops.

Walk Through One Example

Take this array:

[7, 1, 5, 3, 6, 4]

The scan looks like this:

• start with min_so_far = 7, max_diff = 1 - 7 = -6
• at 1, update min_so_far to 1
• at 5, candidate difference is 5 - 1 = 4, so max_diff = 4
• at 3, candidate difference is 3 - 1 = 2, no change
• at 6, candidate difference is 6 - 1 = 5, so max_diff = 5
• at 4, candidate difference is 4 - 1 = 3, no change

Final answer: 5.

The algorithm never compares every pair directly, but it still finds the optimum.

Time and Space Complexity

The runtime is O(n) because the array is scanned once.

The extra space is O(1) because only a small fixed number of variables is stored.

That is the main advantage over the naive O(n^2) solution, which checks every possible pair.

Decide How to Handle Decreasing Arrays

One subtle detail is what answer you want when the array is strictly decreasing.

For example:

[9, 7, 4, 2]

If you require j > i and allow negative results, the answer is -2 from 7 - 9 or 2 - 4 depending on the pair.

If your problem domain treats this like a stock-profit problem and says "do nothing instead of losing money," then you may want to clamp the result to 0.

def max_non_negative_difference(values):
    return max(0, max_difference(values))

Always state which interpretation your problem expects.

Common Pitfalls

The most common mistake is forgetting the order constraint and computing the difference between the global maximum and global minimum even when the minimum appears after the maximum.

Another mistake is initializing max_diff to 0 when the problem allows negative answers. That silently changes the meaning of the problem.

A third issue is using the quadratic solution when the array is large enough that performance matters.

Finally, if the input can have fewer than two elements, handle that case explicitly instead of returning a misleading default.

Summary

• The linear-time solution works by tracking the minimum value seen so far.
• For each element, the best left partner is the smallest earlier element.
• The algorithm runs in O(n) time and O(1) extra space.
• It respects the order constraint i < j naturally.
• Decide whether decreasing arrays should produce a negative answer or 0.
• This is a classic example of replacing pairwise comparison with a running summary of the past.