3.46 Max Gain

3.46.1 Problem Metadata

• Platform: Firecode
• Difficulty: Easy
• URL: N/A
• Tags:
• Techniques: Greedy Array

3.46.2 Description

Given an integer array, return the maximum gain, defined as the largest difference a[j] - a[i] such that j > i. If the array never increases, return 0.

3.46.3 Examples

Input: [0,50,10,100,30]   Output: 100
Input: [100,40,20,10]     Output: 0
Input: [0,100,0,100,0,100] Output: 100

3.46.4 Constraints

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

3.46.5 Solution - One-Pass Greedy

3.46.5.1 Walkthrough

Track the minimum value seen so far while scanning the array. For each element, compute the gain relative to this minimum and update the answer. Update the running minimum whenever a smaller value is encountered.

3.46.5.2 Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

3.46.5.3 Implementation Steps

1. Initialize minValue = +8 and maxGain = 0.
2. For each element x:
   1. Update minValue = min(minValue, x).
   2. Update maxGain = max(maxGain, x - minValue).
3. Return maxGain.

3.46.5.4 Code - Java

public int maxGain(int[] nums) {
    int minValue = Integer.MAX_VALUE;
    int maxGain = 0;

    for (int num : nums) {
        minValue = Math.min(minValue, num);
        maxGain = Math.max(maxGain, num - minValue);
    }

    return maxGain;
}