There are n coins with different value in a line. Two players take turns to take one or two coins from left side until there are no more coins left. The player who take the coins with the most value wins.

Could you please decide thefirstplayer will win or lose?

Have you met this question in a real interview?

Yes

Example

Given values array A =[1,2,2], returntrue.

Given A =[1,2,4], returnfalse.

class Solution {

public:

/\*\*

 \* @param values: a vector of integers

 \* @return: a boolean which equals to true if the first player will win

 \*/

bool firstWillWin\(vector<int> &values\) {

    // write your code here

    if \(values.size\(\) <= 2\) {

        return true;

    }

    int n = values.size\(\);

    vector<int> sfxSum\(n, 0\);

    int sum = 0;

    for \(int i = n - 1; i >= 0; --i\) {

        sum += values\[i\];

        sfxSum\[i\] = sum;

    }

    vector<int> f\(n, 0\);

    f\[n - 1\] = sfxSum\[n - 1\];

    f\[n - 2\] = sfxSum\[n - 2\];

    for \(int i = n - 3; i >= 0; --i\) {

        f\[i\] = max\(values\[i\] + sfxSum\[i + 1\] - f\[i + 1\],

                   values\[i\] + values\[i + 1\] + sfxSum\[i + 2\] - f\[i + 2\]\);

    }

    return f\[0\] > \(sfxSum\[0\] / 2\);

}

};