Question

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$ 到索引 $n-1$ 的这 $k$ 个位置，窗口内卡牌的点数之和记为 $s$，初始答案 $ans$ 的值也为 $s$。这其实是从数组的开头拿走 $0$ 张卡牌的情况。

接下来，我们考虑从数组的开头依次拿 $1, 2, …, k$ 张卡牌的情况，假设取到的卡牌为 $cardPoints[i]$，那么我们将其加入 $s$，由于窗口的长度限制为 $k$，我们需要将 $cardPoints[n-k+i]$ 从 $s$ 中减去，这样我们就可以计算出拿到的 $k$ 张卡牌的点数之和，更新答案 $ans$。

时间复杂度 $O(k)$，其中 $k$ 给题目中给出的整数。空间复杂度 $O(1)$。

class Solution:
  def maxScore(self, cardPoints: List[int], k: int) -> int:
    ans = s = sum(cardPoints[-k:])
    for i, x in enumerate(cardPoints[:k]):
      s += x - cardPoints[-k + i]
      ans = max(ans, s)
    return ans

class Solution {
  public int maxScore(int[] cardPoints, int k) {
    int s = 0, n = cardPoints.length;
    for (int i = n - k; i < n; ++i) {
      s += cardPoints[i];
    }
    int ans = s;
    for (int i = 0; i < k; ++i) {
      s += cardPoints[i] - cardPoints[n - k + i];
      ans = Math.max(ans, s);
    }
    return ans;
  }
}

class Solution {
public:
  int maxScore(vector<int>& cardPoints, int k) {
    int n = cardPoints.size();
    int s = accumulate(cardPoints.end() - k, cardPoints.end(), 0);
    int ans = s;
    for (int i = 0; i < k; ++i) {
      s += cardPoints[i] - cardPoints[n - k + i];
      ans = max(ans, s);
    }
    return ans;
  }
};

func maxScore(cardPoints []int, k int) int {
  n := len(cardPoints)
  s := 0
  for _, x := range cardPoints[n-k:] {
    s += x
  }
  ans := s
  for i := 0; i < k; i++ {
    s += cardPoints[i] - cardPoints[n-k+i]
    ans = max(ans, s)
  }
  return ans
}

function maxScore(cardPoints: number[], k: number): number {
  const n = cardPoints.length;
  let s = cardPoints.slice(-k).reduce((a, b) => a + b);
  let ans = s;
  for (let i = 0; i < k; ++i) {
    s += cardPoints[i] - cardPoints[n - k + i];
    ans = Math.max(ans, s);
  }
  return ans;
}

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

/**
 * @param {number[]} cardPoints
 * @param {number} k
 * @return {number}
 */
var maxScore = function (cardPoints, k) {
  const n = cardPoints.length;
  let s = cardPoints.slice(-k).reduce((a, b) => a + b);
  let ans = s;
  for (let i = 0; i < k; ++i) {
    s += cardPoints[i] - cardPoints[n - k + i];
    ans = Math.max(ans, s);
  }
  return ans;
};

public class Solution {
  public int MaxScore(int[] cardPoints, int k) {
    int n = cardPoints.Length;
    int s = cardPoints[^k..].Sum();
    int ans = s;
    for (int i = 0; i < k; ++i) {
      s += cardPoints[i] - cardPoints[n - k + i];
      ans = Math.Max(ans, s);
    }
    return ans;
  }
}

class Solution {
  /**
   * @param Integer[] $cardPoints
   * @param Integer $k
   * @return Integer
   */
  function maxScore($cardPoints, $k) {
    $n = count($cardPoints);
    $s = array_sum(array_slice($cardPoints, -$k));
    $ans = $s;
    for ($i = 0; $i < $k; ++$i) {
      $s += $cardPoints[$i] - $cardPoints[$n - $k + $i];
      $ans = max($ans, $s);
    }
    return $ans;
  }
}

object Solution {
  def maxScore(cardPoints: Array[Int], k: Int): Int = {
    val n = cardPoints.length
    var s = cardPoints.takeRight(k).sum
    var ans = s
    for (i <- 0 until k) {
      s += cardPoints(i) - cardPoints(n - k + i)
      ans = ans.max(s)
    }
    ans
  }
}

class Solution {
  func maxScore(_ cardPoints: [Int], _ k: Int) -> Int {
    let n = cardPoints.count
    var s = cardPoints.suffix(k).reduce(0, +)
    var ans = s
    for i in 0..<k {
      s += cardPoints[i] - cardPoints[n - k + i]
      ans = max(ans, s)
    }
    return ans
  }
}

# @param {Integer[]} card_points
# @param {Integer} k
# @return {Integer}
def max_score(card_points, k)
  n = card_points.length
  s = card_points[-k..].sum
  ans = s
  k.times do |i|
  s += card_points[i] - card_points[n - k + i]
  ans = [ans, s].max
  end
  ans
end

class Solution {
  fun maxScore(cardPoints: IntArray, k: Int): Int {
    val n = cardPoints.size
    var s = cardPoints.sliceArray(n - k until n).sum()
    var ans = s
    for (i in 0 until k) {
      s += cardPoints[i] - cardPoints[n - k + i]
      ans = maxOf(ans, s)
    }
    return ans
  }
}