C++ O(N) Solution


  • 0
    J
    class Solution {
    public:
        bool PredictTheWinner(vector<int>& nums) {
            int N = nums.size();
            if (N % 2 == 0)
                return true;
            int sum_odd = 0, sum_even = 0;
            for (int i = 0; i < N; i++) {
                if (i & 1)
                    sum_even += nums[i];
                else
                    sum_odd += nums[i];
            }
            if (nums[0] >= abs(sum_even - sum_odd + nums[0]) || nums[N - 1] >= abs(sum_even - sum_odd + nums[N - 1]))
                return true;
            return false;
        }
    };
    

  • 0
    Z
    This post is deleted!

  • 1
    B

    This algorithm does not work if the input size is odd.

    @brendon4565 said in DP O(n^2) + MIT OCW solution explanation:

    Your MIT OCW O(n) solution does not work.

    The professor in the video only described a O(n) strategy for solving the problem when the size of the problem was even. And for good reason. If the size of the problem is odd, then the question is harder.

    An odd-size problem could be decomposed this way. Either the first player picks a[0] and second player must gain at least a[0] more than the first player in the subproblem s[1...n], or , first player picks a[n] and second player must gain at least a[n] more than the first player in the subproblem s[0..n-1]. If in either case the second player cannot achieve this then first player wins.

    Important to note is that second player, in both cases, must solve the problem of whether or not it is possible for him to earn at least k points more than the first player. This O(n) strategy to meet/break even is not sufficient. This new problem isn't quite as strict as the optimization problem that the dp algorithm solves, but I do not know of any strategy to solve this otherwise.

    [0,0,7,6,5,6,1] is an example of a test case that could fail.


Log in to reply
 

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