题解 | 小红的岁晚可可塔

#include <stdio.h>
#define Max(a, b) ((a) > (b) ? (a) : (b))

/**
 * 求最大子数组和（滑动窗口法/Kadane算法变种）
 * @param nums 整数数组
 * @param n 数组长度
 * @return 最大子数组和
 */
int maxAnSum(int* nums, int n){
    int left = 0;        // 左指针（窗口左边界）
    int right;           // 右指针（窗口右边界）
    int maxSum = nums[0]; // 全局最大子数组和（初始化为第一个元素）
    int curSum = 0;       // 当前窗口的和

    for(right = 0; right < n; right++){
        // 1. 将当前元素加入窗口
        curSum += nums[right];

        // 2. 更新全局最大值
        maxSum = Max(maxSum, curSum);

        // 3. 如果当前窗口和为负数，收缩窗口直到和为非负
        //    因为负数窗口对后续求最大和没有帮助
        while(curSum < 0){
            curSum -= nums[left++];  // 移除左边元素，左指针右移
        }
    }

    return maxSum;
}

int main() {
    int n, i, nums[1000001];
    scanf("%d\n", &n);
    for(i = 0; i < n; i++){
        scanf("%d ", &nums[i]);
    }
    int res = maxAnSum(nums, n);
    printf("%d", res);
    return 0;
}

int maxAnSum(int* nums, int n){
    int left = 0, right, maxSum = 0;  // 错误1

    for(right = 0; right < n; right++){
        maxSum += nums[right];         // 错误2

        while(maxSum < maxSum - nums[right])  // 错误3
            maxSum -= nums[left++];    // 错误4
    }

    return maxSum;
}

错误点详细分析：