Maximum Alternating Profit — Problem Statement & Solution Guide

ArraysMediumprefix sum and sign tracking

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Use a Kadane‑like DP with two states (pos, neg) updated in O(1) per element, yielding O(n) time and O(1) extra space.

TopicArrays

Patternprefix sum and sign tracking

TimeO(n)

SpaceO(1)

Problem Description

Given an integer array prices of length n, the profit of a contiguous subarray [l, r] (with r>l) is defined as the alternating sum of successive price differences. Formally, let d_i = prices[i+1]‑prices[i] for l ≤ i < r. Two possible alternating sums exist: S_pos = Σ_{k=0}^{r‑l‑1} (‑1)^k·d_{l+k} (starting with a positive sign) and S_neg = Σ_{k=0}^{r‑l‑1} (‑1)^{k+1}·d_{l+k} (starting with a negative sign). The profit of the segment is max(S_pos, S_neg). Your task is to find the maximum profit over all possible contiguous segments of prices. Output the maximum profit as a 64‑bit signed integer.

DSA Pattern Breakdown

"Maximum Alternating Profit"

medium

WHY DOES IT MATTER?

Alternating‑sign subarray problems appear in finance (buy‑sell‑buy sequences), signal processing, and any scenario where gains and losses must be paired, making the pattern a staple for interviewers testing DP insight beyond classic max‑subarray.

OPTIMIZATION CHALLENGE

The breakthrough is recognizing that extending a subarray flips the sign, so you only need two rolling values (pos and neg) rather than recomputing the whole alternating sum for every candidate interval.

REAL-WORLD CONNECTION

Think of a trader who alternately buys and sells a stock; the profit after each trade flips sign. Optimizing the sequence of trades over a time window mirrors the alternating‑sum subarray, just as a load‑balancer alternates between high‑ and low‑load servers to maximize throughput.

During the interview, write the DP recurrence first, then immediately collapse it to two variables; this shows you can derive O(1) space on the spot and avoids off‑by‑one sign errors.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem reduces to finding a contiguous subarray of the price‑difference array d where the sum alternates signs. A naïve O(n^2) solution enumerates every start‑end pair and computes both alternating sums, which quickly blows up for n up to 10^5. The optimal paradigm is a linear‑time dynamic programming similar to Kadane’s algorithm. By keeping two states for each index – the best alternating sum ending at i with a positive sign (pos) and with a negative sign (neg) – we can update in O(1) per element: pos[i]=max(d[i],neg[i-1]+d[i]); neg[i]=max(-d[i],pos[i-1]-d[i]). The global answer is the maximum of all pos and neg values. This DP captures the decision to either start a new subarray at i or extend the previous one with the opposite sign, yielding an O(n) time and O(1) extra space solution.

Interview Questions on This Problem

Q1How would you modify the solution if the profit definition required the alternating sum to always start with a negative sign?

Swap the roles of the pos and neg DP states or simply take the maximum of the neg state after processing the entire array, because the recurrence already handles both start signs; you just pick the opposite final state.

Q2Can the maximum alternating profit be computed using a segment tree? If so, what information must each node store?

Yes. Each node must store four values: the best pos‑ending sum, best neg‑ending sum, the maximum overall pos sum, and the maximum overall neg sum for its interval, allowing merges that respect sign flipping across the boundary.

Q3In a streaming setting where prices arrive one by one, how would you maintain the answer with O(1) memory per new price?

Maintain the last two DP states (prevPos, prevNeg) and the global maximum; when a new price arrives compute the new difference, update pos = max(diff, prevNeg+diff) and neg = max(-diff, prevPos-diff), then update globals and shift prev values.

Examples

Example 1

Input

5
5 1 4 2 3

Output

Explanation: All possible segments are examined. The segment covering indices 1 to 4 (1‑based) i.e., [1,4,2,3] yields differences [3,‑2,1]. Starting with a positive sign gives 3‑(‑2)+1 = 6, which is larger than the opposite orientation. No other segment produces a profit greater than 6, so the answer is 6.

Example 2

Input

5
10 8 6 4 2

Output

Explanation: Every adjacent pair has a difference of ‑2. For any length‑2 segment the alternating sum starting with a negative sign equals 2, while the opposite orientation gives ‑2. Longer segments cancel out to 0. Hence the maximum achievable profit is 2.

Example 3

Input

6
1 3 2 5 4 7

Output

Explanation: Differences are [2,‑1,3,‑1,3]. Using the whole array and starting with a positive sign the alternating sum is 2‑(‑1)+3‑(‑1)+3 = 10. The opposite orientation yields ‑10, and no shorter segment exceeds 10. Therefore the maximum profit is 10.

Constraints

1 <= prices.length <= 200000
-10^9 <= prices[i] <= 10^9
All calculations fit in 64‑bit signed integer

Optimal Approach & Strategy

Use a Kadane‑like DP with two states (pos, neg) updated in O(1) per element, yielding O(n) time and O(1) extra space.

Brute Force Approach

Enumerate all O(n^2) subarrays, compute both alternating sums for each, and keep the maximum.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

function maxAlternatingProfit(prices) {
    if (prices.length < 2) {
        return 0;
    }
    let maxProfitPos = 0, maxProfitNeg = 0;
    for (let i = 1; i < prices.length; ++i) {
        const diff = prices[i] - prices[i - 1];
        const newMaxProfitPos = Math.max(maxProfitPos, maxProfitNeg + diff);
        const newMaxProfitNeg = Math.max(maxProfitNeg, maxProfitPos - diff);
        maxProfitPos = newMaxProfitPos;
        maxProfitNeg = newMaxProfitNeg;
    }
    return Math.max(maxProfitPos, maxProfitNeg);
}

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let n;
let prices = [];

rl.on('line', (line) => {
    if (n === undefined) {
        n = parseInt(line);
    } else {
        prices.push(parseInt(line));
    }
});

rl.on('close', () => {
    console.log(maxAlternatingProfit(prices));
});

#include <iostream>
#include <vector>
#include <algorithm>

int maxAlternatingProfit(std::vector<int>& prices) {
    if (prices.size() < 2) {
        return 0;
    }

    int maxProfitPos = 0, maxProfitNeg = 0;
    for (size_t i = 1; i < prices.size(); ++i) {
        int diff = prices[i] - prices[i - 1];
        int newMaxProfitPos = std::max(maxProfitPos, maxProfitNeg + diff);
        int newMaxProfitNeg = std::max(maxProfitNeg, maxProfitPos - diff);
        maxProfitPos = newMaxProfitPos;
        maxProfitNeg = newMaxProfitNeg;
    }
    return std::max(maxProfitPos, maxProfitNeg);
}

int main() {
    int n;
    std::cin >> n;
    std::vector<int> prices(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> prices[i];
    }
    std::cout << maxAlternatingProfit(prices) << std::endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static int maxAlternatingProfit(int[] prices) {
        if (prices.length < 2) {
            return 0;
        }
        int maxPos = 0, maxNeg = 0;
        for (int i = 1; i < prices.length; ++i) {
            int diff = prices[i] - prices[i - 1];
            int newMaxPos = Math.max(maxPos, maxNeg + diff);
            int newMaxNeg = Math.max(maxNeg, maxPos - diff);
            maxPos = newMaxPos;
            maxNeg = newMaxNeg;
        }
        return Math.max(maxPos, maxNeg);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] prices = new int[n];
        for (int i = 0; i < n; ++i) {
            prices[i] = sc.nextInt();
        }
        System.out.println(maxAlternatingProfit(prices));
    }
}

def max_alternating_profit(prices):
    if len(prices) < 2:
        return 0
    max_pos, max_neg = 0, 0
    for i in range(1, len(prices)):
        diff = prices[i] - prices[i - 1]
        new_max_pos = max(max_pos, max_neg + diff)
        new_max_neg = max(max_neg, max_pos - diff)
        max_pos, max_neg = new_max_pos, new_max_neg
    return max(max_pos, max_neg)

if __name__ == '__main__':
    n = int(input())
    prices = [int(input()) for _ in range(n)]
    print(max_alternating_profit(prices))

function maxAlternatingProfit(prices) {
    if (prices.length < 2) {
        return 0;
    }
    let maxProfitPos = 0, maxProfitNeg = 0;
    for (let i = 1; i < prices.length; ++i) {
        const diff = prices[i] - prices[i - 1];
        const newMaxProfitPos = Math.max(maxProfitPos, maxProfitNeg + diff);
        const newMaxProfitNeg = Math.max(maxProfitNeg, maxProfitPos - diff);
        maxProfitPos = newMaxProfitPos;
        maxProfitNeg = newMaxProfitNeg;
    }
    return Math.max(maxProfitPos, maxProfitNeg);
}

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let n;
let prices = [];

rl.on('line', (line) => {
    if (n === undefined) {
        n = parseInt(line);
    } else {
        prices.push(parseInt(line));
    }
});

rl.on('close', () => {
    console.log(maxAlternatingProfit(prices));
});

Asked in Top Tech Interviews

Amazon

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.