美文网首页
LeetCode 第 1423 题:可获得的最大点数

LeetCode 第 1423 题:可获得的最大点数

作者: 放开那个BUG | 来源:发表于2024-03-06 15:58 被阅读0次

1、前言

图片.png

2、思路

逆向思维:求拿走的最大值,不如先求剩下牌的最小值,然后用总和减去最小值,就是最大值了。
只需要设置一个 n-k 大的滑动窗口,不停的从头到尾开始滑动就行

3、代码

递归:

public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        Map<Integer, Integer> map = new HashMap<>();
        return dfs(cardPoints, map, k, 0, n - 1, n);
    }

    private int dfs(int[] cardPoints, Map<Integer, Integer> map, int k, int left, int right, int n){
        if(k == 0){
            return 0;
        }
        int posi = left * n + right;
        if(map.containsKey(posi)){
            return map.get(posi);
        }


        int leftSum = cardPoints[left] + dfs(cardPoints, map, k - 1, left + 1, right, n);
        int rightSum = cardPoints[right] + dfs(cardPoints, map, k - 1, left, right - 1, n);

        int max = Math.max(leftSum, rightSum);
        map.put(posi, max);

        return max;
    }

滑动窗口

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int windowSize = n - k, sum = 0;
        for(int i = 0; i < windowSize; i++){
            sum += cardPoints[i];
        }
        int min = sum;
        for(int i = windowSize; i < n; i++){
            sum = sum + cardPoints[i] - cardPoints[i - windowSize];
            min = Math.min(min, sum);
        }
        return Arrays.stream(cardPoints).sum() - min;
    }
}

相关文章

网友评论

      本文标题:LeetCode 第 1423 题:可获得的最大点数

      本文链接:https://www.haomeiwen.com/subject/ilfmkdtx.html