maximum-pulse-value-after-one-subarray-rotation

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> of length <code>n</code>.

Define the pulse value of an integer array <code>arr</code> as the alternating sum starting at index 0: <code>pulse(arr) = arr[0] - arr[1] + arr[2] - arr[3] + ...</code>.

You may perform at most one operation on <code>nums</code>:

<ul>
	<li>Choose two indices <code>l</code> and <code>r</code> such that <code>0 &lt;= l &lt; r &lt; n</code>.</li>
	<li>Left-rotate the subarray <code>nums[l..r]</code> by exactly one position. For example, <code>[a, b, c, d]</code> becomes <code>[b, c, d, a]</code>.</li>
</ul>

Return the maximum pulse value that can be obtained after performing at most one such operation.

&nbsp;
Example 1:

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

Output: 6

Explanation:

<ul>
	<li>The original pulse value is <code>1 - 5 + 2 = -2</code>.</li>
	<li>Rotate the subarray <code>nums[0..1]</code> from <code>[1, 5]</code> to <code>[5, 1]</code>.</li>
	<li>The resulting array is <code>[5, 1, 2]</code> and its pulse value is <code>5 - 1 + 2 = 6</code>, which is the maximum possible.</li>
</ul>
</div>

Example 2:

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

Output: 7

Explanation:

<ul>
	<li>The original pulse value is <code>6 - 4 + 3 = 5</code>.</li>
	<li>Rotate the subarray <code>nums[1..2]</code> from <code>[4, 3]</code> to <code>[3, 4]</code>.</li>
	<li>The resulting array is <code>[6, 3, 4]</code> and its pulse value is <code>6 - 3 + 4 = 7</code>, which is the maximum possible.</li>
</ul>
</div>

Example 3:

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

Output: 2

Explanation:

The original pulse value is <code>9 - 7 = 2</code>, which is already maximum. Thus, no rotation is required.
</div>

&nbsp;
Constraints:

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