Welcome to Subscribe On Youtube

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

  • 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;
    }
}

  • 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;
    }
};

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


  • 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
}


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

All Problems

All Solutions