319. Pick From Either End
Two collectors, Asha and Ben, share a row of treasure chests. Chest i holds nums[i] gold coins. They alternate turns, Asha first. On a turn a collector must take either the leftmost or the rightmost chest still in the row and add its coins to their own pile. When the row is empty the game ends.
Both collectors play perfectly and each tries to finish with as many more coins than the other as possible. Return true if Asha finishes with strictly more coins than Ben, and false otherwise; a tie counts as a failure for Asha. Trying every sequence of picks takes exponential time, so reuse the answers for sub-rows.
Example 1
- Input:
- nums = [2,9,4,5]
- Output:
- true
- Explanation:
Asha takes 5. If Ben then takes 4, Asha takes 9 and Ben is left with 2, so she ends with 14 coins against 6, a lead of 8.
Example 2
- Input:
- nums = [6,3,3,6]
- Output:
- false
- Explanation:
Whatever Asha does, Ben can answer so that both finish with 9 coins, which is a tie, so the answer is false.
Constraints
1 ≤ nums.length ≤ 1000
0 ≤ nums[i] ≤ 104
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n^2)
- Space
- O(n)