Maximum Difference Between Increasing Elements

easy array

Problem

Given a 0-indexed array nums, find the maximum difference nums[j] − nums[i] over all pairs with i < j and nums[i] < nums[j]. If no such pair exists, return −1.

Inputnums = [7,1,5,4]

Output4

nums[2] − nums[1] = 5 − 1 = 4 is the largest.

nums

def maximum_difference(nums):
    min_so_far = nums[0]
    best = -1
    for j in range(1, len(nums)):
        if nums[j] > min_so_far:
            best = max(best, nums[j] - min_so_far)
        else:
            min_so_far = nums[j]
    return best

function maximumDifference(nums) {
  let minSoFar = nums[0], best = -1;
  for (let j = 1; j < nums.length; j++) {
    if (nums[j] > minSoFar) best = Math.max(best, nums[j] - minSoFar);
    else minSoFar = nums[j];
  }
  return best;
}

class Solution {
    public int maximumDifference(int[] nums) {
        int minSoFar = nums[0], best = -1;
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] > minSoFar) best = Math.max(best, nums[j] - minSoFar);
            else minSoFar = nums[j];
        }
        return best;
    }
}

int maximumDifference(vector<int>& nums) {
    int minSoFar = nums[0], best = -1;
    for (int j = 1; j < (int)nums.size(); j++) {
        if (nums[j] > minSoFar) best = max(best, nums[j] - minSoFar);
        else minSoFar = nums[j];
    }
    return best;
}

Explanation

For a fixed later index j, the largest difference nums[j] − nums[i] with i < j comes from pairing it with the smallest element to its left. So we never need to compare all pairs.

We sweep once with a variable minSoFar that holds the minimum of everything seen before the current position. It starts at nums[0].

At each j, if nums[j] is bigger than minSoFar we have a valid increasing pair and update best with the difference. Otherwise nums[j] is a new low, so we move minSoFar down to it for future positions.

Because best starts at -1 and only changes on a genuine increase, the answer is -1 exactly when the array never rises. One pass gives O(n) time, O(1) space.

Example: [7,1,5,4]. minSoFar starts 7; at 1 it drops to 1; at 5 we get 5−1=4 → best 4; at 4 we get 4−1=3, smaller, so best stays 4.

Time: O(n) Space: O(1)