Skip to content

← leetcode

Maximum Difference Between Increasing Elements

· Easy

LeetCode problem 2016

Just use a greedy algorithm; while iterating through the array nums:

  • if the current value is larget than the smallest value seen so far, update the ans if nums[i] - mn is greater

  • else, update mn to be nums[i]

code

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

complexity

  • Time: O(n) where n is the size of nums
  • Space: O(1)

time taken

  • 2 minutes and 28 seconds