滑动窗口实现两端取数最大和的代码错误排查

给定大小为N的整数数组A，你需要从数组A的左端或右端恰好选取B个元素以获得最大和，请找出并返回这个最大可能和。

注：假设B=4、数组A共10个元素，你可以选前四个元素、后四个元素，或1个前端元素+3个后端元素等任意组合，需要返回所有选取方式能得到的最大元素和。

采用反向计算逻辑：从数组两端恰好选取B个元素后，数组剩余的部分一定是一段长度为数组总长度 - B的连续子数组。因此只需要找到该长度下连续子数组的最小和，用数组总和减去这个最小和，就能得到两端选取B个元素的最大和。

初始实现代码如下：

int Solution::solve(vector<int> &A, int B) {
    long long sum=0;
    for(int a:A)
    {
       sum+=a;   //sum of all the elements
    }
    int window=A.size()-B;  
    int j=0;
    long long mini=LONG_MAX;
    long long cur=0; //cur stores sum of current window
    for(int i=0;i<A.size();i++)
    {
        cur+=A[i];  //increase window size by 1
        if(i>=window-1)
        {
            mini=min(mini,cur);
            cur-=A[j];
            j++;    //decrease window size by 1
        }
    }
    return sum-mini;
}

该版本在元素全为负数的超大型测试用例上运行失败：预期返回值为-50293468，函数实际返回值为-50292468，结果存在固定偏差。

调整窗口初始化逻辑后，代码可通过所有测试用例，实现如下：

int Solution::solve(vector<int> &A, int B) {
    long long sum=0;
    for(int a:A)
    {
        sum+=a;
    }

    int window=A.size()-B;
    int j=0;
    long long mini;
    long long cur=0;
    for(int i=0;i<=window-1;i++)
    {
        cur+=A[i];
    }
    mini=cur;
    for(int j=0,i=window;i<A.size();i++,j++)
    {
        cur+=A[i];
        cur-=A[j];
        mini=min(mini,cur);
    }
    return sum-mini;
    
}

核心问题是未处理B == 数组长度（即滑动窗口长度window = 0）的边界场景：

• 当B等于数组总长度时，需要选取数组全部元素，对应剩余的连续子数组长度为0，其和固定为0，此时正确返回值就是数组所有元素的总和。
• 第一版代码中，当window=0时，判断条件i >= window-1等价于i >= -1，循环从i=0开始的每一轮都会进入窗口计算分支：
  • 每轮先把当前元素A[i]累加到cur，此时cur值为单个元素A[i]
  • 随后将cur与mini比较更新最小值，之后立刻减去A[j]把cur重置为0
  • 最终mini会被更新为整个数组中的最小元素值，而非正确的0
• 触发错误的全负测试用例中，数组最小元素为-1000，因此第一版计算结果为sum - (-1000) = sum + 1000，正好对应观测到的偏差：正确值-50293468，错误返回值-50292468，差值恰好为1000。

修正后的代码单独初始化第一个窗口的和，当window=0时，第一个窗口的初始化循环不会执行，cur默认值为0，正好对应长度为0的子数组和，后续滑动过程中cur也始终保持0，因此mini取值正确，完整覆盖了边界场景。

内容的提问来源于stack exchange，提问作者Sneha Sharma