Участник:Hellhoundmipt/predict-the-winner

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/predict-the-winner

Код на scala

object Solution {
    import scala.math.{max, min}
    def PredictTheWinner(nums: Array[Int]): Boolean = {
        val n = nums.length
        if ((n & 1) == 0) true
        else {
            val dp = Array.fill(n)(0)
            for {
                i <- n - 1 to 0 by -1
                j <- i until n
            } if (i == j) dp(i) = nums(i) else dp(j) = max(nums(i) - dp(j), nums(j) - dp(j - 1))
            dp(n - 1) >= 0
        }
    }
}