Iterative O(n^2) Java solution. Based on OCW lecture.


  • 0
    K
    public class Solution {
        public boolean PredictTheWinner(int[] nums) {
            int n = nums.length;
            int sum = 0;
            int[][] dp = new int[n][n];
            for(int i = 0; i < n; ++i)
            {
                dp[i][i] = nums[i];
                sum += nums[i];
            }
            for(int i = 0; i < n - 1; ++i)
            {
                dp[i][i+1] = Math.max(nums[i], nums[i+1]);
            }
            int max1, max2, j;
            for(int l = 2; l < n; ++l)
            {
                for(int i = 0; i < n-l; ++i)
                {
                    j = i + l;
                    max1 = Math.min(dp[i+2][j], dp[i+1][j-1]);
                    max2 = Math.min(dp[i][j-2], dp[i+1][j-1]);
                    dp[i][j] = Math.max(max1 + nums[i], max2 + nums[j]);
                }
            }
            return dp[0][n-1] >= (sum-dp[0][n-1]);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.