longest-alternating-subarray-after-removing-at-most-one-element

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 an integer array <code>nums</code>.

A subarray <code>nums[l..r]</code> is alternating if one of the following holds:

<ul>
	<li><code>nums[l] &lt; nums[l + 1] &gt; nums[l + 2] &lt; nums[l + 3] &gt; ...</code></li>
	<li><code>nums[l] &gt; nums[l + 1] &lt; nums[l + 2] &gt; nums[l + 3] &lt; ...</code></li>
</ul>

In other words, if we compare adjacent elements in the subarray, then the comparisons alternate between strictly greater and strictly smaller.

You can remove at most one element from <code>nums</code>. Then, you select an alternating subarray from <code>nums</code>.

Return an integer denoting the maximum length of the alternating subarray you can select.

A subarray of length 1 is considered alternating.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [2,1,3,2]

Output: 4

Explanation:

<ul>
	<li>Choose not to remove elements.</li>
	<li>Select the entire array <code>[2, 1, 3, 2]</code>, which is alternating because <code>2 &gt; 1 &lt; 3 &gt; 2</code>.</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: nums = [3,2,1,2,3,2,1]

Output: 4

Explanation:

<ul>
	<li>Choose to remove <code>nums[3]</code> i.e., <code>[3, 2, 1, 2, 3, 2, 1]</code>. The array becomes <code>[3, 2, 1, 3, 2, 1]</code>.</li>
	<li>Select the subarray <code>[3, 2, 1, 3, 2, 1]</code>.</li>
</ul>
</div>

Example 3:

<div class="example-block">
Input: nums = [100000,100000]

Output: 1

Explanation:

<ul>
	<li>Choose not to remove elements.</li>
	<li>Select the subarray <code>[100000, 100000]</code>.</li>
</ul>
</div>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 105</code></li>
</ul>

Weekly Contest 487

weekly-contest-487

longestAlternating

Senior Staff

Longest Alternating Subarray After Removing At Most One Element

Array

Dynamic Programming

Enumeration

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 an integer array nums.

A subarray nums[l..r] is alternating if one of the following holds:

 * nums[l] < nums[l + 1] > nums[l + 2] < nums[l + 3] > ...
 * nums[l] > nums[l + 1] < nums[l + 2] > nums[l + 3] < ...

In other words, if we compare adjacent elements in the subarray, then the comparisons alternate between strictly greater and strictly smaller.

You can remove at most one element from nums. Then, you select an alternating subarray from nums.

Return an integer denoting the maximum length of the alternating subarray you can select.

A subarray of length 1 is considered alternating.

 

Example 1:

Input: nums = [2,1,3,2]

Output: 4

Explanation:

 * Choose not to remove elements.
 * Select the entire array [2, 1, 3, 2], which is alternating because 2 > 1 < 3 > 2.

Example 2:

Input: nums = [3,2,1,2,3,2,1]

Output: 4

Explanation:

 * Choose to remove nums[3] i.e., [3, 2, 1, 2, 3, 2, 1]. The array becomes [3, 2, 1, 3, 2, 1].
 * Select the subarray [3, 2, 1, 3, 2, 1].

Example 3:

Input: nums = [100000,100000]

Output: 1

Explanation:

 * Choose not to remove elements.
 * Select the subarray [100000, 100000].

 

Constraints:

 * 2 <= nums.length <= 105
 * 1 <= nums[i] <= 105