leetcode-1423

This week’s daily question, do algorithm, have imagination, enough to fully explore the known conditions.

Topic

https://leetcode-cn.com/problems/maximum-points-you-can-obtain-from-cards/

Solution

Backtracking

This problem can only be taken from the beginning or the end at a time, so the decision-making process can be a binary tree.

We use two pointers to the end of the untraversed team head, respectively, as pointers to the left subtree and the right subtree.

const trackback = (cardPoints, k, count, left, right, result) => {
    if (count = k) {
        return result;
    } else {
        const leftresult = trackback(cardPoints, k, count + 1, left + 1, right, result + cardPoints[left]);
        const rightresult = trackback(cardPoints, k, count + 1, left, right - 1, result + cardPoints[right]);
        return Math.max(leftresult, rightresult);
    }
}

var maxScore = function(cardPoints, k) {
    return trackback(cardPoints, k, 0, 0, cardPoints.length - 1, 0);
};

Reverse thinking + sliding window

The above solution is a conventional solution, but in fact there is a known condition of this problem that we have not made good use of.

That is, each time you can only take the value from the beginning or the end, that is to say, after completing k values, the rest is continuous.

Then assuming the length of the array is n, after taking k values, there are n-k contiguous arrays left.

We only need to find the minimum value of the consecutive array of n-k to derive the maximum value.

var maxScore = function(cardPoints, k) {
    const n = cardPoints.length;
    //sliding window size n-k
    const windowSize = n - k;
    Select the first n-k as the initial value
    let sum = 0;
    for (let i = 0; i < windowSize; ++i) {
        sum += cardPoints[i];
    }
    let minSum = sum;
    for (let i = windowSize; i < n; ++i) {
        //Every time the sliding window moves one space to the right, the value of the elements entering the window from the right is increased, and the value of the elements leaving the window from the left is decreased
        sum += cardPoints[i] - cardPoints[i - windowSize];
        minSum = Math.min(minSum, sum);
    }
    let totalSum = 0;
    for (let i = 0; i < n; i++) {
        totalSum += cardPoints[i];
    }
    return totalSum - minSum;
};