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
Recommendation Algorithm Flow for Maximum Difference Between Increasing Elements

Solution Approach

Track minVal. For each element, if > minVal compute diff; else update minVal.

function solution(nums) {
  if (nums.length < 2) return -1;
  var minVal = nums[0];
  var maxDiff = -1;
  for (var i = 1; i < nums.length; i++) {
    if (nums[i] > minVal) {
      var diff = nums[i] - minVal;
      if (diff > maxDiff) maxDiff = diff;
    } else {
      minVal = nums[i];
    }
  }
  return maxDiff;
}

Time O(n), Space 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;
    }
}