Skip to content

Latest commit

 

History

History
199 lines (154 loc) · 5.07 KB

README.md

File metadata and controls

199 lines (154 loc) · 5.07 KB

1423. 可获得的最大点数

English Version

题目描述

几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。

每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。

你的点数就是你拿到手中的所有卡牌的点数之和。

给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

 

示例 1：

输入：cardPoints = [1,2,3,4,5,6,1], k = 3
输出：12
解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。

示例 2：

输入：cardPoints = [2,2,2], k = 2
输出：4
解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。

示例 3：

输入：cardPoints = [9,7,7,9,7,7,9], k = 7
输出：55
解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。

示例 4：

输入：cardPoints = [1,1000,1], k = 1
输出：1
解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。

示例 5：

输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
输出：202

 

提示：

  • 1 <= cardPoints.length <= 10^5
  • 1 <= cardPoints[i] <= 10^4
  • 1 <= k <= cardPoints.length

解法

要让左右两侧共 k 个元素和最大，可以转换为求中间连续数组 n - k 个元素和最小值 mi，然后用数组总和 s 减去 mi 得到答案。

Python3

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        s = [0] * (n + 1)
        for i in range(n):
            s[i + 1] = s[i] + cardPoints[i]
        mi = inf
        for i in range(n):
            j = i + (n - k) - 1
            if j < n:
                mi = min(mi, s[j + 1] - s[i])
        return s[-1] - mi

Java

class Solution {

    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int[] s = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + cardPoints[i];
        }
        int mi = Integer.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            int j = i + (n - k) - 1;
            if (j < n) {
                mi = Math.min(mi, s[j + 1] - s[i]);
            }
        }
        return s[n] - mi;
    }
}

C++

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int n = cardPoints.size();
        vector<int> s(n + 1);
        for (int i = 0; i < n; ++i) s[i + 1] = s[i] + cardPoints[i];
        int mi = INT_MAX;
        for (int i = 0; i < n; ++i) {
            int j = i + (n - k) - 1;
            if (j < n) mi = min(mi, s[j + 1] - s[i]);
        }
        return s[n] - mi;
    }
};

Go

func maxScore(cardPoints []int, k int) int {
	n := len(cardPoints)
	s := make([]int, n+1)
	for i := 0; i < n; i++ {
		s[i+1] = s[i] + cardPoints[i]
	}
	mi := math.MaxInt64
	for i := 0; i < n; i++ {
		j := i + (n - k) - 1
		if j < n {
			mi = min(mi, s[j+1]-s[i])
		}
	}
	return s[n] - mi
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

TypeScript

function maxScore(cardPoints: number[], k: number): number {
    const n = cardPoints.length;
    let sum = cardPoints.slice(0, n - k).reduce((r, v) => r + v, 0);
    let min = sum;
    for (let i = 0; i < k; i++) {
        sum += cardPoints[n - k + i] - cardPoints[i];
        min = Math.min(min, sum);
    }
    return cardPoints.reduce((r, v) => r + v, 0) - min;
}

Rust

impl Solution {
    pub fn max_score(card_points: Vec<i32>, k: i32) -> i32 {
        let (k, n) = (k as usize, card_points.len());
        let mut sum = card_points.iter().take(n - k).sum::<i32>();
        let mut min = sum;
        for i in 0..k {
            sum += card_points[n - k + i] - card_points[i];
            min = min.min(sum);
        }
        card_points.iter().sum::<i32>() - min
    }
}

...