</>EmbeddedInterview

How do you find the maximum difference arr[j] - arr[i] with j > i?

MediumArrays & Strings (Coding Round)

Short answer: Scan left to right, keeping the minimum value seen so far. At each element compute arr[j] - min_so_far and keep the largest. One pass, O(n) time, O(1) space. This is the same as "best time to buy and sell a stock once".

#include <stddef.h>

/* n >= 2 */
int max_difference(const int *arr, size_t n)
{
    int min_so_far = arr[0];
    int best = arr[1] - arr[0];
    for (size_t j = 1; j < n; j++) {
        if (arr[j] - min_so_far > best)
            best = arr[j] - min_so_far;
        if (arr[j] < min_so_far)
            min_so_far = arr[j];
    }
    return best;
}
/* {2, 3, 10, 6, 4, 8, 1} -> 8  (10 - 2) */

Dry run

j arr[j] min before arr[j]-min best
1 3 2 1 1
2 10 2 8 8
3 6 2 4 8
4 4 2 2 8
5 8 2 6 8
6 1 2 -1 8

Why the order of the two ifs matters: compute the difference before updating the minimum, so j > i holds. Starting the loop at j = 1 avoids comparing an element with itself.

Why initialise best = arr[1] - arr[0] and not 0: for a strictly decreasing array such as {9, 7, 4}, the correct answer is -2. Starting at 0 would report a difference that does not exist. (If the question is "maximum profit", where not trading is allowed, 0 is correct; clarify.)

Naive version: two nested loops over all pairs, O(n²).

Follow-up: "Return the indices too": store the index whenever min_so_far changes and record (min_index, j) whenever best improves.