#3828
Final Element After Subarray Deletions
medium · 40.1% accepted · 109 likes · top 19%
array · math · brainteaser · game theory
Description
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 that r - l + 1 < m, where m is 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.
Solution