问题链接:https://www.interviewbit.com/problems/pick-from-both-sides/
我正在使用滑动窗口来解决它,方法是找到最小的连续总和子数组,然后从 totalSum 中减去它。
这会被接受:
int Solution::solve(vector<int> &A, int B) {
int n=A.size();
int totalSum=0, sum=0, minn;
for(int i=0; i<A.size(); i++) totalSum+=A[i];
int ws=0, we=n-B-1;
for(int i=ws; i<=we; i++) sum+=A[i];
minn=sum;
ws++;we++;
while(we < n) {
sum+=(A[we]-A[ws-1]);
minn=min(minn, sum);
ws++; we++;
}
return totalSum-minn;
}
这不是为什么?(在硬测试用例上给出错误的答案)
int Solution::solve(vector<int> &A, int B) {
int n=A.size();
int totalSum=0, sum=0, minn;
for(int i=0; i<A.size(); i++) totalSum+=A[i];
int ws=0, k=n-B-1;
minn = INT_MAX;
for(int we=ws; we<n; we++) {
sum+=A[we];
if(we>=k) {
minn=min(minn, sum);
sum-=A[ws];
ws++;
}
}
return totalSum-minn;
}
如何修复第二个实现?