Maximum Alternating Subsequence Sum - Practice Coding Problems

Maximum Alternating Subsequence Sum - Problem

The alternating sum of a 0-indexed array is defined as the sum of the elements at even indices minus the sum of the elements at odd indices.

For example, the alternating sum of [4,2,5,3] is (4 + 5) - (2 + 3) = 4.

Given an array nums, return the maximum alternating sum of any subsequence of nums (after reindexing the elements of the subsequence).

A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements' relative order. For example, [2,7,4] is a subsequence of [4,2,3,7,2,1,4] (the underlined elements), while [2,4,2] is not.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,2,5,3]

› Output: 7

💡 Note: Optimal subsequence is [4,2,5] with alternating sum 4-2+5 = 7

Example 2 — Single Element

$ Input: nums = [5,6,7,8]

› Output: 8

💡 Note: Take just the largest element [8] with alternating sum 8

Example 3 — Two Elements

$ Input: nums = [6,2,1,2,4,5]

› Output: 10

💡 Note: Optimal subsequence is [6,1,5] with alternating sum 6-1+5 = 10

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [4,2,5,3]

Find Subsequence

Choose elements to maximize alternating sum

Calculate Sum

Compute alternating sum: pos-neg+pos-neg...

Key Takeaway

🎯 Key Insight: Think of it as buying and selling stocks - buy low, sell high to maximize profit!

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to think of this as a stock trading problem where we buy low and sell high. The optimal approach uses dynamic programming to track maximum profit when holding vs not holding stocks. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Approach	O(n)	O(1)	Think of it as buying and selling stocks to maximize profit
Bottom-Up Dynamic Programming	O(n)	O(1)	Track maximum sum ending at even and odd positions iteratively
Brute Force - Generate All Subsequences	O(n × 2ⁿ)	O(n)	Generate all possible subsequences and calculate their alternating sums
Memoization (Top-Down DP)	O(n)	O(n)	Use recursion with memoization to avoid recomputing subproblems

Greedy Approach — Algorithm Steps

Step 1: Start with 0 stocks, track current balance
Step 2: For each element, decide whether to buy, sell, or do nothing
Step 3: Always prefer selling high and buying low to maximize profit

Visualization

Tap to expand

Step-by-Step Walkthrough

Buy Low

Purchase stocks when price is low

Sell High

Sell stocks when price is high

Profit

Total profit from all transactions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long solution(int* nums, int numsSize) {
    // Think of it as stock trading: buy low, sell high
    // Start with 0 stocks (can buy) and 0 profit
    long long hold = 0;  // Maximum profit when holding stocks
    long long sold = 0;  // Maximum profit when not holding stocks
    
    for (int i = 0; i < numsSize; i++) {
        // Two choices at each step:
        // 1. Buy stock (if we weren't holding): sold - nums[i]
        // 2. Sell stock (if we were holding): hold + nums[i]
        long long newHold = (hold > sold - nums[i]) ? hold : (sold - nums[i]);
        long long newSold = (sold > hold + nums[i]) ? sold : (hold + nums[i]);
        
        hold = newHold;
        sold = newSold;
    }
    
    return sold;  // We want to end without holding stocks
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[20];
    int numsSize = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    long long result = solution(nums, numsSize);
    printf("%lld\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array, constant work per element

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

52.0K Views

Medium Frequency

~25 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler