Final Element After Subarray Deletions
You are given an integer array nums.
Two players, Alice and Bob, play a game in turns, with Alice playing first.
- In each turn, the current player chooses any subarray
nums[l..r]such thatr - l + 1 < m, wheremis the current length of the array. - The selected subarray is removed, and the remaining elements are concatenated to form the new array.
- The game continues until only one element remains.
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.
Example 1
Input
nums = [1,5,2]Output
2One optimal strategy is for Alice to remove
[1], then Bob removes [5], leaving 2 as the final element.Example 2
Input
nums = [3,7]Output
7Alice removes
[3], leaving [7], so Bob cannot play and the final element is 7.Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5