2016. Maximum Difference Between Increasing Elements

Given a 0-indexed integer array nums of size n, find the maximum difference nums[j] - nums[i] such that 0 <= i < j < n and nums[i] < nums[j]. Return the maximum difference; if no such pair exists, return -1.

Example 1

Input: nums = [7, 1, 5, 4]
Output: 4
Explanation:
The maximum difference occurs at i = 1 and j = 2, where nums[j] - nums[i] = 5 - 1 = 4.
Note that for i = 1 and j = 0, nums[j] - nums[i] = 7 - 1 = 6, but since i > j, it is not valid.

Example 2

Input: nums = [9, 4, 3, 2]
Output: -1
Explanation:
There is no valid pair (i, j) such that i < j and nums[i] < nums[j].

Example 3

Input: nums = [1, 5, 2, 10]
Output: 9
Explanation:
The maximum difference occurs at i = 0 and j = 3, where nums[j] - nums[i] = 10 - 1 = 9.

Constraints

• n == nums.length
• 2 <= n <= 1000
• 1 <= nums[i] <= 10^9

Method One: Prefix Minimum

Idea and Algorithm

When we fix j, the index i must satisfy 0 <= i < j and we want nums[i] to be as small as possible. We can iterate over j while maintaining the minimum of the prefix nums[0..j-1], denoted as premin. Then:

• If nums[j] > premin, update the answer with nums[j] - premin.
• Otherwise, update the prefix minimum: premin = nums[j].

Code

C++

class Solution {
public:
    int maximumDifference(vector<int>& nums) {
        int n = nums.size();
        int ans = -1, premin = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > premin) {
                ans = max(ans, nums[i] - premin);
            } else {
                premin = nums[i];
            }
        }
        return ans;
    }
};

Java

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

C#

public class Solution {
    public int MaximumDifference(int[] nums) {
        int n = nums.Length;
        int ans = -1, premin = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > premin) {
                ans = Math.Max(ans, nums[i] - premin);
            } else {
                premin = nums[i];
            }
        }
        return ans;
    }
}

Python3

class Solution:
    def maximumDifference(self, nums: List[int]) -> int:
        n = len(nums)
        ans, premin = -1, nums[0]

        for i in range(1, n):
            if nums[i] > premin:
                ans = max(ans, nums[i] - premin)
            else:
                premin = nums[i]
        
        return ans

C

#define MAX(a, b) ((a) > (b) ? (a) : (b))

int maximumDifference(int* nums, int numsSize){
    int ans = -1, premin = nums[0];
    for (int i = 1; i < numsSize; ++i) {
        if (nums[i] > premin) {
            ans = MAX(ans, nums[i] - premin);
        } else {
            premin = nums[i];
        }
    }
    return ans;
}

JavaScript

var maximumDifference = function(nums) {
    const n = nums.length;
    let ans = -1, premin = nums[0];
    for (let i = 1; i < n; ++i) {
        if (nums[i] > premin) {
            ans = Math.max(ans, nums[i] - premin);
        } else {
            premin = nums[i];
        }
    }
    return ans;
};

Go

func maximumDifference(nums []int) int {
    ans := -1
    preMin := nums[0]
    for i := 1; i < len(nums); i++ {
        if nums[i] > preMin {
            ans = max(ans, nums[i]-preMin)
        } else {
            preMin = nums[i]
        }
    }
    return ans
}

func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}

Complexity Analysis

• Time Complexity: $O(n)$. We traverse the array nums exactly once.
• Space Complexity: $O(1)$. Only constant extra space is used.