2036. Maximum Alternating Subarray Sum

Problem Description

In this problem, we are given an array of integers, where the array is 0-indexed, meaning indexing starts from 0. A subarray is defined as a contiguous non-empty sequence of elements within the array. The alternating subarray sum is a special kind of sum where we alternately add and subtract the elements of the subarray starting with addition. For example, if the subarray starts at index i and ends at index j, then the alternating sum would be calculated as nums[i] - nums[i+1] + nums[i+2] - ... +/- nums[j].

The objective is to find the maximum alternating subarray sum that can be obtained from any subarray within the given integer array nums.

Intuition

To solve this problem, we need to take into consideration that the sum we are looking to maximize can switch from positive to negative numbers and vice versa because of the alternating addition and subtraction. A brute force approach would involve checking all possible subarrays, but this would not be efficient, especially for large arrays.

Consequently, we turn to dynamic programming (DP) to optimize our process. The solution builds on the concept that the maximum alternating sum ending at any element in the array (which is either added or subtracted) can be based on the maximum sum we've computed up to the previous element.

We keep two accumulators, f and g, at each step of our iteration through the array. f represents the maximum alternating subarray sum where the last element is added, and g is where the last element is subtracted. At each iteration, f can either be the previous g (plus the current element, if g was at least 0, indicating a previous alternating subarray contribution), or it can directly be the current element if including the previous sequence doesn't yield a larger sum. Concurrently, g becomes the previous f minus the current element.

By maintaining and updating these two values at each step, we can ensure that the maximum alternating subarray sum can be computed in a single pass, thus significantly reducing the time complexity from what a brute force method would entail. The answer is the highest value achieved by either f or g during the iteration.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Solution Approach

The solution employs a dynamic programming (DP) approach to solve the problem efficiently. The key insight of the DP approach is to define two states that represent the maximum alternating subarray sum at each position i in the array nums.

f is defined to be the maximum alternating subarray sum ending with nums[i] being added.
g is defined to be the maximum alternating subarray sum ending with nums[i] being subtracted.

The solution initiates f and g with the value -inf to represent that initially, there's no subarray, hence the alternating sum is the smallest possible (negative infinity). As the array is traversed, f and g will be updated for each element.

Here’s how f and g get updated for every element in nums:

f gets updated to the maximum of g + nums[i] or 0 plus nums[i]. In essence, this step decides whether to extend the alternating subarray by adding the current number to the previously best alternating sum ending with a subtracted number, or to start fresh with the current number if no profitable alternating subarray exists before it (in which case g would be non-positive).
g gets updated to f - nums[i] from before the update in step 1. This step effectively chooses to continue the alternating subarray by transitioning from addition to subtraction at this element.

The overall answer, ans, will be the maximum of all such f and g values computed. This ensures that at the end of the iteration through all elements in nums, ans will store the maximum alternating subarray sum of any potential subarray within nums.

The mathematical formulas involved in updating f and g are as follows:

f = max(g + nums[i], nums[i]) which equates to f = max(g, 0) + nums[i] since adding a negative g would be less beneficial than just starting fresh from nums[i].

g = f_previous - nums[i]

Lastly, for each iteration, ans is updated to the larger of itself, f or g. At the end of the loop, ans will hold the final maximum alternating subarray sum, which the function returns.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10][100, 33, 30][10, 12, 20]

I don’t know

Example Walkthrough

Let's consider a small example to illustrate the solution approach with the array nums = [3, -1, 4, -3, 5].

Initially, we set f and g to negative infinity, representing no sum because we haven't started the process, and ans to negative infinity to track the maximum sum we discover.

Starting with the first element (3), we update f since no previous sum exists. So, f becomes max(-inf, 0) + 3 = 3. We update ans with the maximum of ans, f and g, so ans = max(-inf, 3, -inf) = 3. No need to update g yet since we only have one element.

For the second element (-1), we now have a subarray to consider:

g gets updated to the previous value of f minus the current element, so g = 3 - (-1) = 4.
f gets updated to the max of current g plus the element or just the element, so f = max(0 + -1, 4 + -1) = 3.
ans now becomes max(3, 4, 3) = 4.

Moving on to the third element (4):

g gets updated to f from the previous step minus the current element, so g = 3 - 4 = -1.
f is updated to be max(0 + 4, -1 + 4) = 4 because the previous g was negative.
ans is updated to max(4, -1, 4) = 4.

For the fourth element (-3):

g gets updated to f from the previous step minus the current element, so g = 4 - (-3) = 7.
f is not any larger when updating with the current g, so f remains max(0 + -3, 7 + -3) = 4.
ans is updated to max(4, 7, 4) = 7.

Finally, for the last element (5):

g gets updated, g = 4 - 5 = -1.
f gets updated since g is negative, f = max(0 + 5, -1 + 5) = 5.
ans is updated to max(7, -1, 5) = 7.

After completing the iteration, ans holds the value of 7, which is the maximum alternating subarray sum of any subarray within nums. The subarray contributing to this max sum in our example is [-1, 4, -3], resulting in an alternating sum of -1 + 4 - (-3) = 7.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maximumAlternatingSubarraySum(self, nums: List[int]) -> int:
5        # Initialize variables to store the maximum sum found, 
6        # and temporary sums for even and odd indexed elements.
7        max_sum = float('-inf')  # Use float('-inf') for negative infinity
8        sum_even_idx = float('-inf')  # Sum at an even index of the alternated subarray
9        sum_odd_idx = float('-inf')  # Sum at an odd index of the alternated subarray
10      
11        # Loop through each number in the input array
12        for num in nums:
13            # Update the sum at an even index. It is the greater of
14            # the previous sum at an odd index (if it was a valid subarray sum) plus the current number,
15            # or starting a new subarray from the current number.
16            sum_even_idx, sum_odd_idx = max(sum_odd_idx, 0) + num, sum_even_idx - num
17          
18            # Update the maximum sum found so far by comparing with the new sums
19            # obtained from the even and odd indexed subarrays.
20            max_sum = max(max_sum, sum_even_idx, sum_odd_idx)
21      
22        # Return the maximum alternating subarray sum that was found.
23        return max_sum
24

1class Solution {
2    public long maximumAlternatingSubarraySum(int[] nums) {
3        // Initialize a large value as "infinity".
4        final long INF = 1L << 60;
5
6        // Initialize `maxSum` to negative infinity which will store
7        // the final result, the maximum alternating subarray sum.
8        long maxSum = -INF;
9
10        // Initialize variables to keep track of alternate subarray
11        // sums during the iteration.
12        long evenPositionSum = -INF;
13        long oddPositionSum = -INF;
14
15        // Iterate through the `nums` array.
16        for (int num : nums) {
17            // Calculate temporary sum for the subarray ending at an even position.
18            long tempEvenSum = Math.max(oddPositionSum, 0) + num;
19
20            // Update the sum for the subarray ending at an odd position.
21            oddPositionSum = evenPositionSum - num;
22
23            // Update `evenPositionSum` with the new calculated value.
24            evenPositionSum = tempEvenSum;
25
26            // Update `maxSum` to be the maximum of itself, `evenPositionSum`, and `oddPositionSum`.
27            maxSum = Math.max(maxSum, Math.max(evenPositionSum, oddPositionSum));
28        }
29
30        // Return the computed maximum alternating subarray sum.
31        return maxSum;
32    }
33}
34

1#include <vector>
2#include <algorithm> // For using the max function
3
4class Solution {
5public:
6    // Function to find the maximum alternating subarray sum.
7    long long maximumAlternatingSubarraySum(vector<int>& nums) {
8        using ll = long long; // Define long long as ll for easy use
9        const ll negativeInfinity = 1LL << 60; // Define a very large negative number to compare with
10      
11        ll maxSum = -negativeInfinity; // Initialize maxSum with a very large negative value
12        ll sumEven = -negativeInfinity; // Sum ending at even index (alternating subarray sum starting with positive term)
13        ll sumOdd = -negativeInfinity; // Sum ending at odd index (alternating subarray sum starting with negative term)
14      
15        // Loop through each number in the array to build alternating sums
16        for (int num : nums) {
17            ll newSumEven = max(sumOdd, 0LL) + num; // Calculate new even index sum
18            sumOdd = sumEven - num; // Calculate new odd index sum
19            sumEven = newSumEven; // Update even index sum
20          
21            // Update the maxSum with the maximum value among maxSum, sumEven, and sumOdd
22            maxSum = max({maxSum, sumEven, sumOdd});
23        }
24      
25        return maxSum; // Return the maximum alternating subarray sum
26    }
27};
28

1function maximumAlternatingSubarraySum(nums: number[]): number {
2    // Initialize maxSum to the smallest number to ensure it gets updated
3    // f represents the maximum sum of an alternating subarray ending with a positive term
4    // g represents the maximum sum of an alternating subarray ending with a negative term
5    let maxSum = Number.MIN_SAFE_INTEGER, positiveTermSum = Number.MIN_SAFE_INTEGER, negativeTermSum = Number.MIN_SAFE_INTEGER;
6  
7    for (const num of nums) {
8        // Update positiveTermSum: either start a new subarray from current num (if g is negative) or add num to the previous subarray (g + num)
9        positiveTermSum = Math.max(negativeTermSum, 0) + num;
10        // Update negativeTermSum: subtract current num from the previous subarray to alternate the sign
11        negativeTermSum = positiveTermSum - num;
12        // Update maxSum to the maximum value of maxSum, positiveTermSum, and negativeTermSum at each iteration
13        maxSum = Math.max(maxSum, positiveTermSum, negativeTermSum);
14    }
15
16    return maxSum;
17}
18

Not Sure What to Study? Take the 2-min Quiz：

Time and Space Complexity

The given Python code defines a method maximumAlternatingSubarraySum which calculates the maximum sum of any non-empty subarray from nums, where the sign of the elements in the subarray alternates.

Time Complexity

To understand the time complexity, let's go through the code:

The function iterates through the array nums once using a for loop (line 4).
Within each iteration of the for loop, it performs a constant number of operations: updating f, g, and ans (line 5).
No additional loops or recursive calls are present.

Since the number of operations within the loop does not depend on the size of the array, and the loop runs n times where n is the number of elements in nums, the time complexity is linear with respect to the length of the array, which we represent as O(n).

Space Complexity

Now, let's examine the space complexity:

The solution uses a fixed number of extra variables ans, f, and g (line 3), independent of the input size.
No additional data structures dependent on the input size are utilized.
No recursive calls are made that would add to the call stack and therefore increase space complexity.

Taking the above points into consideration, the space complexity of the algorithm is constant, denoted as O(1) since the additional space used does not scale with the size of the input.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological SortUniform Cost SearchMonotonic StackMemoization

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2036. Maximum Alternating Subarray Sum

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings