leetcode_1423 可获得的最大点数

本文主要是介绍leetcode_1423 可获得的最大点数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题意

给定一个数组，每次只能从头和尾进行选择。
选择k次当前头或者尾，问能取到的最大值。
可获得的最大点数

2. 题解

主要难点是意识到这是一个滑动窗口问题。

2.1 滑动窗口

令数组长度为$sz$
令$s\_w(pos,k)$为其实点为$pos$,长度为$k$的滑窗。
则求解的问题为$max(sum(s\_w(i,k))),(sz-k)\le i\le sz-1ori=0$

• 正向
  $Time:O(k),Space:O(1)$

class Solution {
public:int maxScore(vector<int>& cardPoints, int k) {int sz = cardPoints.size();int bpos = sz - k;int ans = 0;int sum = 0;for ( int i = sz - k; i < sz - 1; ++i)sum += cardPoints[i];for ( int i = bpos; i < sz; ++i) {int idx = (i + k - 1) % sz;sum += cardPoints[idx];ans = max(ans, sum);sum -= cardPoints[i];}sum = std::accumulate(cardPoints.begin(), cardPoints.begin() + k, 0);ans = max(sum, ans);return ans;}
};

直接求首尾的滑动窗口复杂点，由于数组固定则总和固定。
求最大的$Sum(s\_w(pos,k))$可以转化为 求最小的$Sum(s\_w(pow,sz-k))$。
最后再用总和减去最小的$sz-k$滑窗即可。

注意：由于是首尾滑窗，所以sz-k的滑窗不能出现首尾相连情况

• 逆向
  $Time:O(n),Space:O(1)$

class Solution {
public:int maxScore(vector<int>& cardPoints, int k) {int sz = cardPoints.size();int m = sz - k;int win_sum = 0;int tot_sum = std::accumulate(cardPoints.begin(), cardPoints.end(), 0);if ( m == 0)return tot_sum;if ( m > 1) {win_sum = std::accumulate(cardPoints.begin(), cardPoints.begin() + m - 1,0);}int win_min = INT_MAX;for (int i = 0;i < sz - m + 1; ++i) {int idx = (i + m - 1) % sz;win_sum += cardPoints[idx];win_min = min(win_min, win_sum);win_sum -= cardPoints[i];}return tot_sum - win_min;}
};

2.2 前缀和与后缀和

由于最终的情况无非，在前缀中取$k_1$,在后缀中取$k_2$,$k_1+k_2=k$。
所以我们可以通过计算$Prefix(i),0\le i\le k;Suffix(j),0\le j\le k$
求出每一种情况即:$Prefix(x)+Suffix(k-x)$的值来判断大小。

• 前后缀分解
  $Time:O(k),Space:O(k)$

注意：前后缀累加只累计k轮

class Solution {
public:int maxScore(vector<int>& cardPoints, int k) {vector<int> prefix;vector<int> suffix;int preSum = 0;int sufSum = 0;int sz = cardPoints.size();for ( int i = 0; i < k + 1;++i) {prefix.push_back(preSum);suffix.push_back(sufSum);if ( i != k) {preSum += cardPoints[i];sufSum += cardPoints[sz - 1 - i];}}int ans = 0;for ( int i = 0; i < k + 1; ++i) {ans = max(ans, prefix[i] + suffix[k  - i]);}return ans;}
};

这篇关于leetcode_1423 可获得的最大点数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---