Solution 1: Recursion
func PredictTheWinner(_ nums: [Int]) -> Bool {
return winner(nums, 0, nums.count-1, 1) >= 0
}
private func winner(_ nums: [Int], _ start: Int, _ end: Int, _ turn: Int) -> Int {
if start == end {
return turn * nums[start]
}
let a = turn * nums[start] + winner(nums, start+1, end, -turn)
let b = turn * nums[end] + winner(nums, start, end-1, -turn)
return turn * max(a*turn, b*turn)
}
Solution 2: Dynamic programming
func PredictTheWinner(_ nums: [Int]) -> Bool {
var dp = Array(repeating: Array(repeating: 0, count: nums.count), count: nums.count)
for i in stride(from: 0, to: nums.count, by: 1) {
dp[i][i] = nums[i]
}
for len in stride(from: 1, to: nums.count, by: 1) {
var i = 0
for j in stride(from: len, to: nums.count, by: 1) {
dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])
i += 1
}
}
return dp[0][nums.count-1] >= 0
}