{x}
blog image

Maximum Alternating Subarray Sum

Solution Explanation for Maximum Alternating Subarray Sum

This problem asks to find the maximum alternating subarray sum within a given integer array. An alternating subarray sum is calculated as nums[i] - nums[i+1] + nums[i+2] - ... +/- nums[j]. The most efficient approach is using dynamic programming.

Approach: Dynamic Programming

Instead of brute-forcing all possible subarrays, we use dynamic programming to efficiently track the maximum alternating sum ending at each index. We maintain two variables:

  • f: Represents the maximum alternating subarray sum ending at the current index with a positive sign for the last element.
  • g: Represents the maximum alternating subarray sum ending at the current index with a negative sign for the last element.

Iteration:

For each element nums[i]:

  1. Update f: The maximum alternating sum ending at i with a positive sign is either:

    • The sum including nums[i] (i.e., g + nums[i]), if g is positive (extending a positive sum); otherwise we start a new subarray with nums[i] alone.
    • nums[i] if g is negative or zero, so adding g would reduce the sum.

  2. Update g: The maximum alternating sum ending at i with a negative sign is simply f - nums[i]. We are extending the previous positive sum (f) by subtracting nums[i].

  3. Update ans: The overall maximum sum is the maximum among the current ans, f, and g.

Initialization:

We initialize f and g to negative infinity (-inf) to handle cases where all elements are negative. ans is initialized the same way.

Time Complexity: O(n) - We iterate through the array once.

Space Complexity: O(1) - We only use a constant number of variables.

Code Implementation in Multiple Languages

Here's the implementation of this approach in several languages:

Python:

import math
 
class Solution:
    def maximumAlternatingSubarraySum(self, nums: list[int]) -> int:
        ans = f = g = -math.inf  # Initialize to negative infinity
        for x in nums:
            f, g = max(g, 0) + x, f - x # Update f and g as explained above
            ans = max(ans, f, g)       # Track the overall maximum
        return ans

Java:

class Solution {
    public long maximumAlternatingSubarraySum(int[] nums) {
        long ans = Long.MIN_VALUE;  // Java's equivalent of negative infinity
        long f = Long.MIN_VALUE;
        long g = Long.MIN_VALUE;
        for (int x : nums) {
            long ff = Math.max(g, 0) + x;
            g = f - x;
            f = ff;
            ans = Math.max(ans, Math.max(f, g));
        }
        return ans;
    }
}

C++:

#include <limits> // for numeric_limits
#include <algorithm>
 
class Solution {
public:
    long long maximumAlternatingSubarraySum(vector<int>& nums) {
        long long ans = numeric_limits<long long>::min(); // C++'s negative infinity
        long long f = numeric_limits<long long>::min();
        long long g = numeric_limits<long long>::min();
        for (int x : nums) {
            long long ff = max(g, 0LL) + x;
            g = f - x;
            f = ff;
            ans = max({ans, f, g}); // Use max({a,b,c}) for multiple comparisons
        }
        return ans;
    }
};

JavaScript:

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumAlternatingSubarraySum = function(nums) {
    let ans = -Infinity;
    let f = -Infinity;
    let g = -Infinity;
    for (let x of nums) {
        let ff = Math.max(g, 0) + x;
        g = f - x;
        f = ff;
        ans = Math.max(ans, f, g);
    }
    return ans;
};

Go:

import "math"
 
func maximumAlternatingSubarraySum(nums []int) int64 {
	ans, f, g := int64(math.MinInt64), int64(math.MinInt64), int64(math.MinInt64) //Go's negative infinity
	for _, x := range nums {
		f, g = max(g, 0)+int64(x), f-int64(x)
		ans = max(ans, max(f, g))
	}
	return ans
}
 
func max(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

These code examples all implement the same dynamic programming solution, showing how the core algorithm can be expressed in different programming languages. Remember to handle potential integer overflow by using long long (or equivalent) data types when necessary.