Greedy Scan for Maximum Positive Difference

Hey Devs! 👋

Let’s explore a fundamental and insightful problem: 2016. Maximum Difference Between Increasing Elements.

It teaches us a classic pattern — tracking minimums to find profitable differences — very similar to the Best Time to Buy and Sell Stock problem!

📝 Problem Statement

You're given an integer array nums.

Find the maximum difference nums[j] - nums[i] such that:

• 0 <= i < j < n
• nums[i] < nums[j]

If no such pair exists, return -1.

🔍 Example

Input: nums = [7,1,5,4]
Output: 4
Explanation:

• Choose i = 1 (value 1) and j = 2 (value 5)
• Difference: 5 - 1 = 4

Input: nums = [9,4,3,2]
Output: -1
There’s no i < j where nums[i] < nums[j]

💡 Intuition

To get the maximum positive difference:

• Keep track of the smallest number seen so far (mn)
• At each step j, calculate nums[j] - mn only if nums[j] > mn
• Update mn if the current number is smaller

Simple, right? Let’s see how it works.

⚙️ C++ Implementation

class Solution {
 public:
  int maximumDifference(vector<int>& nums) {
    int ans = -1;
    int mn = nums[0];

    for (int i = 1; i < nums.size(); ++i) {
      if (nums[i] > mn)
        ans = max(ans, nums[i] - mn);
      mn = min(mn, nums[i]);
    }

    return ans;
  }
};

🌐 JavaScript Version

var maximumDifference = function(nums) {
    let ans = -1;
    let minSoFar = nums[0];

    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > minSoFar)
            ans = Math.max(ans, nums[i] - minSoFar);
        minSoFar = Math.min(minSoFar, nums[i]);
    }

    return ans;
};

🐍 Python Version

def maximumDifference(nums: List[int]) -> int:
    ans = -1
    mn = nums[0]

    for i in range(1, len(nums)):
        if nums[i] > mn:
            ans = max(ans, nums[i] - mn)
        mn = min(mn, nums[i])

    return ans

🧪 Test Cases

Input: [7,1,5,4]
Output: 4    // 5 - 1

Input: [9,4,3,2]
Output: -1   // No valid pair

Input: [1,5,2,10]
Output: 9    // 10 - 1

Input: [2,2,2,2]
Output: -1   // No increasing pair

⏱️ Time & Space Complexity

Time: O(n) — Single pass through the array
Space: O(1) — Constant extra space

✅ Final Thoughts

This problem is a pattern you must master — track the minimum, look for gains, and compare!

It builds core understanding for:

• Stock market problems
• Sliding window or greedy patterns
• Optimization in linear scans

📌 Tip: You can even extend this for related variants like tracking both max and min simultaneously.

Drop a ❤️ if this helped, and stay tuned for more bitesize breakdowns!

Happy coding, folks! 🚀