Introduction

This problem asks for the largest value of A[j] - A[i] subject to j > i. The key constraint is the index order: you are not just looking for the maximum minus the minimum value anywhere in the array, but for the best later element minus an earlier element.

Why the Naive Approach Is Too Slow

A direct solution compares every valid pair of indices and keeps the largest difference. That works, but it costs O(n^2) time because each element is compared with many later elements.

For an interview-sized input that may be acceptable. For large arrays, it is wasteful because you keep recomputing information you could have remembered from earlier positions.

The Linear-Time Idea

As you scan left to right, keep track of two things:

1. The smallest value seen so far.
2. The best difference seen so far.

At position j, the best candidate partner for A[j] is not every earlier element. It is simply the smallest earlier value. If you already know that minimum, you can evaluate A[j] - min_so_far in constant time.

That leads to an O(n) algorithm with O(1) extra space.

Python Implementation

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    best = values[1] - values[0]
7
8    for current in values[1:]:
9        best = max(best, current - min_so_far)
10        min_so_far = min(min_so_far, current)
11
12    return best
13
14
15nums = [8, 1, 2, 4, 6, 3]
16print(max_difference(nums))

For the sample input, the answer is 5, produced by 6 - 1.

Step-by-Step Walkthrough

Take the array [8, 1, 2, 4, 6, 3].

• Start with min_so_far = 8.
• At 1, the candidate difference is 1 - 8 = -7. Update min_so_far to 1.
• At 2, the candidate difference is 2 - 1 = 1. Best so far becomes 1.
• At 4, the candidate difference is 4 - 1 = 3. Best becomes 3.
• At 6, the candidate difference is 6 - 1 = 5. Best becomes 5.
• At 3, the candidate difference is 3 - 1 = 2. Best stays 5.

The scan finishes with 5 as the maximum valid difference.

Handling Arrays That Only Decrease

One subtle point is whether negative answers are allowed. In most formulations, yes. If the array is strictly decreasing, the maximum valid A[j] - A[i] is still negative because every later value is smaller than the earlier one.

For example, in [9, 7, 4, 1], the answer is -2, from 7 - 9. That is why the implementation initializes best from the first valid pair instead of from 0. Using 0 would incorrectly claim that no-loss choices exist when they do not.

Why This Is Related to Stock Profit Problems

This question is structurally similar to the one-transaction stock-profit problem. There too, you track the minimum purchase price seen so far and compute the best later sale. The difference is that some stock variants clamp the answer to zero when no profit is possible, while this array question often expects the mathematically largest difference even if it is negative.

Common Pitfalls

• Ignoring the j > i constraint and simply subtracting the global minimum from the global maximum.
• Initializing the best difference to 0, which breaks cases where every valid difference is negative.
• Replacing the running minimum too late or too early in the loop. Update order matters.
• Using a quadratic nested loop when the problem explicitly asks for linear time.
• Forgetting edge cases such as arrays with fewer than two elements.

Summary

• The problem is to maximize A[j] - A[i] with j > i.
• A running minimum plus running best difference solves it in O(n) time.
• The correct partner for each A[j] is the smallest earlier value, not every earlier value.
• Negative answers are valid when the array decreases throughout.
• This is the same core pattern used in one-pass stock-profit algorithms.