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>

Biweekly Contest 187

biweekly-contest-187

maximumValue

Senior

Maximum Value of an Alternating Sequence

Math

Greedy

Accepted

Wrong Answer

Memory Limit Exceeded

Output Limit Exceeded

Time Limit Exceeded

Runtime Error

Internal Error

Compile Error

Timeout

Restrictions Failed

cangjie

react

vanillajs

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