Code Logo

Maximum Difference Between Increasing Elements

Published at24 Jul 2026
Created by
Easy 0 views
Like0

Given an array of integers nums, find the maximum difference between any two elements nums[j] - nums[i] where j > i and nums[j] > nums[i]. If no such increasing pair exists, return -1.

This is equivalent to finding the maximum profit from a single buy-sell stock transaction. The DP approach uses one pass: track the minimum value seen so far. For each element at position i, if it is greater than the current minimum, compute the difference and update the maximum difference if this one is larger. If the element is smaller than the current minimum, it becomes the new minimum for future comparisons.

The key insight is that the best profit at any sell point depends only on the lowest price seen before that point. This one-pass DP maintains only the minimum state and the maximum difference state, using O(1) extra space and O(n) time.

Edge cases include empty or single-element arrays (return -1), strictly decreasing arrays where no profit is possible (return -1), and arrays with equal values throughout (return -1).

The maximum difference problem uses the minimum value seen so far as its only state variable. This pattern is the foundation for the single-stock profit problem and illustrates how DP can capture all necessary history in a single scalar value.

Example Input & Output

Example 1
Input
[1,5,2,10]
Output
9
Explanation

Buy 1 sell 10.

Example 2
Input
[1]
Output
-1
Explanation

Single.

Example 3
Input
[7,1,5,4]
Output
4
Explanation

Buy 1 sell 5.

Example 4
Input
[2,2,2]
Output
-1
Explanation

Equal.

Example 5
Input
[9,4,3,2]
Output
-1
Explanation

Decreasing.

Algorithm Flow

Recommendation Algorithm Flow for Maximum Difference Between Increasing Elements

Solution Approach

Find the maximum difference between two elements where the larger element appears after the smaller one. Track the minimum value seen so far while iterating. For each element, compute the difference between it and the current minimum. Keep track of the maximum difference found. If the array is decreasing, return -1.

function maxProfit(prices) {
  var minPrice = prices[0], maxDiff = -1;
  for (var i = 1; i < prices.length; i++) {
    if (prices[i] > minPrice) {
      if (prices[i] - minPrice > maxDiff) maxDiff = prices[i] - minPrice;
    } else {
      minPrice = prices[i];
    }
  }
  return maxDiff;
}

The minimum price is updated when a lower price is found. For each higher price, the potential profit is compared to the running max. If the array is strictly decreasing, maxDiff stays -1 since no pair satisfies the condition.

Time complexity is O(n), space complexity is O(1).

Best Answers

java
class Solution {
    public int solution(int[] nums) {
        if (nums.length<2) return -1;
        int m=nums[0],d=-1;
        for (int i=1;i<nums.length;i++) {
            if (nums[i]>m) {
                int x=nums[i]-m;
                if (x>d) d=x;
            } else m=nums[i];
        }
        return d;
    }
}