Skip to main content
Talentd

Maximum Value of an Alternating Sequence - Solution & Explanation

MediumMathGreedy8 min read
Practice this problem

Problem Statement

You are given three integers n, s, and m.

A sequence seq of integers of length n is considered valid if:

  • seq[0] = s.
  • The sequence is alternating, meaning that either:
    • seq[0] > seq[1] < seq[2] > ..., or
    • seq[0] < seq[1] > seq[2] < ....
  • For every adjacent pair, |seq[i] - seq[i - 1]| <= m.

A sequence of length 1 is considered alternating.

Return the maximum possible element that can appear in any valid sequence.

 

Example 1:

Input: n = 4, s = 3, m = 5

Output: 12

Explanation:

  • One valid sequence is [3, 8, 7, 12].
  • The maximum element in the sequence is 12.

Example 2:

Input: n = 2, s = 4, m = 3

Output: 7

Explanation:

  • One valid sequence is [4, 7].
  • The maximum element in the sequence is 7.

 

Constraints:

  • 1 <= n, s <= 109
  • 1 <= m <= 105

Approach Overview

Problem Overview: You need to build an alternating sequence that maximizes the final value while following alternating addition and subtraction rules. The challenge is deciding whether to include the current number and which alternating state it belongs to.

Approach 1: Brute Force Recursion (O(2^n) time, O(n) space)

The direct approach tries every possible subsequence and alternates between adding and subtracting values. At each index, you either skip the number or include it in the current alternating position. This works for understanding the state transition, but the recursion tree grows exponentially. Use this approach only for very small inputs or for deriving the recurrence relation before optimization.

Approach 2: Dynamic Programming with Memoization (O(n) time, O(n) space)

Store the best answer for each index and alternating state using a memo table. The two states usually represent whether the next chosen element should be added or subtracted. Each recursive call performs constant work after memoization, reducing repeated calculations. This is the standard top-down dynamic programming optimization for alternating sequence problems.

Approach 3: Iterative DP State Compression (O(n) time, O(1) space)

The optimal solution tracks only two running values: the best score when the current element is treated as a positive contribution and the best score when it is treated as a negative contribution. Iterate through the array once and update both states using previous values. This removes the DP array entirely and keeps memory constant. Interviewers usually expect this version because it shows you understand DP state transitions and optimization.

Recommended for interviews: Start by explaining the brute force recursion to show the alternating-choice structure. Then move to the compressed DP solution with two states. The O(n) time and O(1) space approach is the strongest answer because it combines clean state modeling with optimal performance. Problems like this also overlap with greedy transition reasoning and sequence optimization patterns.

Solution

If n = 1, the sequence contains only the starting value s, so the answer is s.

Otherwise, the sequence length is at least 2. Since the absolute difference between adjacent elements is at most m, and the sequence must strictly alternate up and down, to maximize some element we should repeatedly "rise by m, then fall by 1": the fall step is taken as the minimum value 1 so that the next rise has the largest possible room.

Construct the sequence in a "rise first" pattern:

$ s,\ s+m,\ s+m-1,\ s+2m-1,\ s+2m-2,\ ldots

With length n, we can complete \lfloor n / 2 \rfloor rises, and the peak after the k-th rise is s + k(m - 1) + 1. Therefore, the maximum element is:

s + \left\lfloor \frac{n}{2} \right\rfloor (m - 1) + 1

Starting with a fall only decreases the values first and cannot produce a larger peak, so the construction above is optimal.

The time complexity is O(1), and the space complexity is O(1)$.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force RecursionO(2^n)O(n)Useful for deriving recurrence relations or validating small cases
DP with MemoizationO(n)O(n)General solution with clear recursive state transitions
Iterative DP State CompressionO(n)O(1)Best choice for interviews and large input constraints

Video Solution

3993. Maximum Value of an Alternating Sequence (Leetcode Medium) • Programming Live with Larry • 106 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Maximum Value of an Alternating Sequence easy or hard?
Maximum Value of an Alternating Sequence is generally considered a medium-level dynamic programming problem. The recurrence is straightforward once you identify the alternating states, but recognizing the optimal transition can take practice.
Maximum Value of an Alternating Sequence Python/Java solution
Python solutions typically use iterative DP with two variables for concise implementation. Java solutions follow the same transition logic with integer or long variables depending on constraints. Both versions achieve O(n) time complexity.
How to solve Maximum Value of an Alternating Sequence in O(n)?
Iterate through the array while maintaining two DP states representing alternating positions. For each value, update the best possible positive-state score and negative-state score using previous results. This converts the recursive transition into a linear scan.
What is the best approach for Maximum Value of an Alternating Sequence?
The best approach uses dynamic programming with two compressed states. One state tracks the best value when the current number contributes positively, and the other tracks the best value when it contributes negatively. This solution runs in O(n) time and O(1) space.
Is Maximum Value of an Alternating Sequence asked at Google/Amazon/Meta?
Alternating subsequence and DP state-transition problems are common in interviews at Google, Amazon, Meta, and similar companies. Interviewers often use them to test optimization skills, recurrence design, and space reduction techniques.
What data structure is used in Maximum Value of an Alternating Sequence?
The core solution primarily uses dynamic programming states stored in variables or arrays. No advanced data structure is required. Most implementations use simple integer variables for constant-space optimization.
What is the time complexity of Maximum Value of an Alternating Sequence?
The optimal dynamic programming solution runs in O(n) time because each element is processed exactly once. Space complexity can be reduced to O(1) by storing only the previous alternating states instead of a full DP table.

Ready to solve this problem?

Practice Maximum Value of an Alternating Sequence with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer