2016. Maximum Difference Between Increasing Elements

Time: O(n)

Space: O(1)

Intuition

Maximum difference where larger element comes after smaller element. Track minimum seen so far, compute diff at each step.

Algorithm

1min_so_far = nums[0]. max_diff = -1.
2For each i from 1: if nums[i] > min_so_far: max_diff = max(max_diff, nums[i]-min_so_far). Update min_so_far.

Common Pitfalls

•Must have j > i and nums[j] > nums[i]. Track minimum to the left. Return -1 if no valid pair.

2016.cs

// Approach: Track running minimum; for each element compute diff with running min; take max.
// Time: O(n) Space: O(1)

public class Solution
{
    public int MaximumDifference(int[] nums)
    {
        // Initialize the minimum value to a very large value
        int minVal = int.MaxValue;
        // Initialize the answer to -1, assuming there is no positive difference found
        int maxDiff = -1;

        // Loop through each number in the input array
        foreach (int num in nums)
        {
            // If the current number is greater than the minimum value found so far
            if (num > minVal)
            {
                // Update the maximum difference with the greater value between the current maximum difference
                // and the difference between the current number and the minimum value found so far
                maxDiff = Math.Max(maxDiff, num - minVal);
            }
            else
            {
                // If the current number is not greater than the minimum value found so far,
                // then update the minimum value to the current number
                minVal = num;
            }
        }

        // Return the maximum difference found, or -1 if no positive difference exists
        return maxDiff;
    }
}

Was this solution helpful?