Alternating Sum Maximization — Problem Statement & Solution Guide

ArraysMediumMixed

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Arrays and solve the Alternating Sum Maximization 2 problem optimally.

TopicArrays

PatternMixed

TimeO(n)

SpaceO(1)

Problem Description

Given an integer array nums, select a subsequence (possibly the whole array) preserving the original order. Starting with a plus sign, alternately add and subtract the chosen elements. The goal is to maximise the resulting total. Return the maximum achievable alternating sum. The subsequence may contain a single element, and you may stop at any position; you are not required to use all elements.

DSA Pattern Breakdown

"Alternating Sum Maximization"

medium

WHY DOES IT MATTER?

The alternating‑sign pattern appears in many financial and signal‑processing scenarios where gains and losses are interleaved; mastering it equips engineers to reason about optimal profit sequences, error‑correction codes, and load‑balancing cycles.

OPTIMIZATION CHALLENGE

The breakthrough is realizing that only the best ‘+’ and best ‘‑’ sums so far are needed; you don’t need the full DP table. This reduces both time from exponential to linear and space from O(n) to O(1).

REAL-WORLD CONNECTION

Think of stock trading with unlimited transactions: buying a stock is a ‘‑’ operation (cash out) and selling is a ‘+’ operation (cash in). Maximising profit over a price series is exactly the alternating sum maximization problem.

During an interview, compute bestPlus and bestMinus on the fly, update them in the same loop, and keep a running answer as the maximum bestPlus seen – this shows you understand state compression and can write clean, constant‑space code.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem can be modelled as a dynamic programming task with two states: the maximum alternating sum ending with a ‘+’ sign (let’s call it bestPlus) and the maximum alternating sum ending with a ‘‑’ sign (bestMinus). When we process each element x, we have two choices – either start a new subsequence with x as a plus term, or extend an existing subsequence by toggling the sign. Hence bestPlus = max(previous bestPlus, x, bestMinus + x) and bestMinus = max(previous bestMinus, bestPlus - x). This recurrence captures the optimal sub‑structure: the best result up to index i depends only on the best results up to i‑1. A naïve enumeration of all subsequences would require O(2^n) time, which explodes even for moderate n, because each element can be either taken or skipped and the sign flips depend on the order of picks. By collapsing the DP to just two scalar variables we achieve O(n) time and O(1) extra space, which is optimal for a single‑pass array problem.

The key insight is that we never need to remember the entire subsequence, only the best achievable sum for each parity of the next operation. This mirrors the classic “maximum alternating subsequence sum” or “stock‑buy‑sell with unlimited transactions” pattern, where buying corresponds to a ‘‑’ operation and selling to a ‘+’. The algorithm therefore reduces to a simple linear scan, updating bestPlus and bestMinus in constant time per element, guaranteeing scalability to the largest input constraints.

Interview Questions on This Problem

Q1How would you formulate a DP solution for the alternating sum maximization and what states would you keep?

Define two DP states: dpPlus[i] – maximum alternating sum for a subsequence ending at i with a ‘+’ sign, and dpMinus[i] – same but ending with a ‘‑’ sign. The transitions are dpPlus[i]=max(dpPlus[i‑1], nums[i], dpMinus[i‑1]+nums[i]) and dpMinus[i]=max(dpMinus[i‑1], dpPlus[i‑1]-nums[i]). The answer is max over all dpPlus values.

Q2If the problem required the subsequence length to be exactly k, how would you adapt the solution?

Introduce an extra dimension for length, e.g., dpPlus[i][len] and dpMinus[i][len], where len ranges from 1 to k. Transitions remain similar but you only update states when len increments, leading to O(n·k) time and O(k) space after rolling arrays.

Q3Why does the greedy‑like two‑variable solution work for this problem, whereas a simple greedy pick‑largest‑available approach fails?

Because the sign alternates, the contribution of a later element depends on the parity of the number of previously chosen elements. The two‑variable DP captures this dependency exactly, while a naïve greedy that only looks at current magnitude ignores the future sign impact and can miss optimal subsequences.

Examples

Example 1

Input

[4,2,5,1]

Output

Explanation: Choose 4,2,5 → 4−2+5=7, which is larger than any other alternating selection.

Example 2

Input

[-1,-2,-3]

Output

-1

Explanation: Taking only the first element gives -1. Adding any further negative number would decrease the total because the next operation would be subtraction.

Example 3

Input

[10,-5,6,-2,3]

Output

Explanation: Select all elements: 10−5+6−2+3=12. Any omission either removes a positive contribution or forces a larger subtraction, so 12 is optimal.

Constraints

1<=nums.length<=100000
-1000000000<=nums[i]<=1000000000
Result fits in 64-bit signed integer
Time complexity O(n)
Auxiliary space O(1)

Optimal Approach & Strategy

Use a linear DP with two variables (bestPlus, bestMinus) that are updated for each element, yielding O(n) time and O(1) extra space.

Brute Force Approach

Enumerate every possible subsequence, compute its alternating sum, and keep the maximum – exponential time.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxAlternatingSum = function(nums) {
    if (nums.length === 0) return 0;
    
    // plus: maximum sum ending with a plus sign
    // minus: maximum sum ending with a minus sign
    let plus = nums[0];
    let minus = 0;
    
    for (let i = 1; i < nums.length; i++) {
        const newPlus = Math.max(plus, minus + nums[i]);
        const newMinus = Math.max(minus, plus - nums[i]);
        plus = newPlus;
        minus = newMinus;
    }
    
    return Math.max(plus, minus);
};

// Driver code
const nums = [4, 2, 5, 1];
console.log(maxAlternatingSum(nums));

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    long long maxAlternatingSum(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        // plus: maximum sum ending with a plus sign
        // minus: maximum sum ending with a minus sign
        long long plus = nums[0];
        long long minus = 0;
        
        for (int i = 1; i < nums.size(); i++) {
            long long newPlus = max(plus, minus + nums[i]);
            long long newMinus = max(minus, plus - nums[i]);
            plus = newPlus;
            minus = newMinus;
        }
        
        return max(plus, minus);
    }
};

int main() {
    vector<int> nums = {4, 2, 5, 1};
    Solution sol;
    cout << sol.maxAlternatingSum(nums) << endl;
    return 0;
}

import java.util.*;

class Solution {
    public long maxAlternatingSum(int[] nums) {
        if (nums.length == 0) return 0;
        
        // plus: maximum sum ending with a plus sign
        // minus: maximum sum ending with a minus sign
        long plus = nums[0];
        long minus = 0;
        
        for (int i = 1; i < nums.length; i++) {
            long newPlus = Math.max(plus, minus + nums[i]);
            long newMinus = Math.max(minus, plus - nums[i]);
            plus = newPlus;
            minus = newMinus;
        }
        
        return Math.max(plus, minus);
    }
    
    public static void main(String[] args) {
        int[] nums = {4, 2, 5, 1};
        Solution sol = new Solution();
        System.out.println(sol.maxAlternatingSum(nums));
    }
}

from typing import List

class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        # plus: maximum sum ending with a plus sign
        # minus: maximum sum ending with a minus sign
        plus = nums[0]
        minus = 0
        
        for i in range(1, len(nums)):
            new_plus = max(plus, minus + nums[i])
            new_minus = max(minus, plus - nums[i])
            plus = new_plus
            minus = new_minus
        
        return max(plus, minus)

if __name__ == "__main__":
    nums = [4, 2, 5, 1]
    sol = Solution()
    print(sol.maxAlternatingSum(nums))

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxAlternatingSum = function(nums) {
    if (nums.length === 0) return 0;
    
    // plus: maximum sum ending with a plus sign
    // minus: maximum sum ending with a minus sign
    let plus = nums[0];
    let minus = 0;
    
    for (let i = 1; i < nums.length; i++) {
        const newPlus = Math.max(plus, minus + nums[i]);
        const newMinus = Math.max(minus, plus - nums[i]);
        plus = newPlus;
        minus = newMinus;
    }
    
    return Math.max(plus, minus);
};

// Driver code
const nums = [4, 2, 5, 1];
console.log(maxAlternatingSum(nums));

Asked in Top Tech Interviews

PhonePePayPal

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.