maximum-value-of-an-alternating-sequence

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given three integers <code>n</code>, <code>s</code>, and <code>m</code>.

A sequence <code>seq</code> of integers of length <code>n</code> is considered valid if:

<ul>
	<li><code>seq[0] = s</code>.</li>
	<li>The sequence is alternating, meaning that either:
	<ul>
		<li><code>seq[0] &gt; seq[1] &lt; seq[2] &gt; ...</code>, or</li>
		<li><code>seq[0] &lt; seq[1] &gt; seq[2] &lt; ...</code>.</li>
	</ul>
	</li>
	<li>For every adjacent pair, <code>|seq[i] - seq[i - 1]| &lt;= m</code>.</li>
</ul>

A sequence of length 1 is considered alternating.

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

&nbsp;
Example 1:

<div class="example-block">
Input: n = 4, s = 3, m = 5

Output: 12

Explanation:

<ul>
	<li>One valid sequence is <code>[3, 8, 7, 12]</code>.</li>
	<li>The maximum element in the sequence is 12.</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: n = 2, s = 4, m = 3

Output: 7

Explanation:

<ul>
	<li>One valid sequence is <code>[4, 7]</code>.</li>
	<li>The maximum element in the sequence is 7.</li>
</ul>
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n, s &lt;= 109</code></li>
	<li><code>1 &lt;= m &lt;= 105</code></li>
</ul>