Skip to content

3993. Maximum Value of an Alternating Sequence

Description

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

Solutions

Solution 1: Greedy

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)\).

1
2
3
4
5
class Solution:
    def maximumValue(self, n: int, s: int, m: int) -> int:
        if n == 1:
            return s
        return s + n // 2 * (m - 1) + 1

1
2
3
4
5
6
7
8
class Solution {
    public long maximumValue(int n, int s, int m) {
        if (n == 1) {
            return s;
        }
        return (long) s + (long) (n / 2) * (m - 1) + 1;
    }
}

1
2
3
4
5
6
7
8
9
class Solution {
public:
    long long maximumValue(int n, int s, int m) {
        if (n == 1) {
            return s;
        }
        return 1LL * s + 1LL * (n / 2) * (m - 1) + 1;
    }
};

1
2
3
4
5
6
func maximumValue(n int, s int, m int) int64 {
    if n == 1 {
        return int64(s)
    }
    return int64(s) + int64(n/2)*int64(m-1) + 1
}

1
2
3
4
5
6
function maximumValue(n: number, s: number, m: number): number {
    if (n === 1) {
        return s;
    }
    return s + Math.floor(n / 2) * (m - 1) + 1;
}

Comments