LeetCode 1423. 可获得的最大点数 (前缀和)
原题链接
中等
作者:
GRID
,
2021-02-06 23:13:12
,
所有人可见
,
阅读 307
分析
- 如果k比最大长度大,直接输出数组总和即可
- k比最大长度小,要进行排列组合。
选前0个,后k个
选前1个,后k-1个
…
选前k个,后0个
为了方便计算总和,可以预先求前缀和,之后就在区间和中取最大值。
C++ 代码
class Solution {
public:
int ans=INT_MIN;
int maxScore(vector<int>& cardPoints, int k) {
int n=cardPoints.size();
if(k>=n) //k比数组长,返回总和
{
ans=0;
for(auto x:cardPoints) ans+=x;
return ans;
}
else{
int s[n+1];
memset(s,0,sizeof s);
for(int i=1;i<=n;i++) //求前缀和,下标从1~n
s[i]=cardPoints[i-1]+s[i-1];
for(int i=0;i<=k;i++)
{
ans=max(ans,s[i]+s[n]-s[n-(k-i)]); //选择最大的前缀和
}
}
return ans;
}
};