final-element-after-subarray-deletions

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

Two players, Alice and Bob, play a game in turns, with Alice playing first.

<ul>
	<li>In each turn, the current player chooses any subarray <code>nums[l..r]</code> such that <code>r - l + 1 &lt; m</code>, where <code>m</code> is the current length of the array.</li>
	<li>The selected subarray is removed, and the remaining elements are concatenated to form the new array.</li>
	<li>The game continues until only one element remains.</li>
</ul>

Alice aims to maximize the final element, while Bob aims to minimize it. Assuming both play optimally, return the value of the final remaining element.

&nbsp;
Example 1:

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

Output: 2

Explanation:

One valid optimal strategy:

<ul>
	<li>Alice removes <code>[1]</code>, array becomes <code>[5, 2]</code>.</li>
	<li>Bob removes <code>[5]</code>, array becomes <code>[2]</code>​​​​​​​. Thus, the answer is 2.</li>
</ul>
</div>

Example 2:

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

Output: 7

Explanation:

Alice removes <code>[3]</code>, leaving the array <code>[7]</code>. Since Bob cannot play a turn now, the answer is 7.
</div>

&nbsp;
Constraints:

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