带限制的最大子数组和问题（限制子数组长度不超过L） 题目描述 给定一个整数数组 nums 和一个正整数 L ，要求找到一个长度 不超过 L 的连续子数组，使其和最大。例如，当 nums = [1, -2, 3, 4, -1, 2] ， L = 3 时，长度不超过3的最大和子数组是 [3, 4, -1] 或 [3, 4] ，其和为6。 解题思路 问题分析 ：此问题在经典最大子数组和（Kadane算法）基础上增加了子数组长度不超过L的限制。直接枚举所有长度不超过L的子数组会达到O(nL)的时间复杂度，当L较大时效率低。 关键观察 ：对于以索引 j 结尾且长度不超过L的子数组，其最大和可表示为 prefix[j] - min(prefix[i]) ，其中 j - L ≤ i ≤ j ， prefix[] 是前缀和数组。这转化为在宽度为L的滑动窗口中维护前缀和的最小值。 算法选择 ：使用单调队列（双端队列）优化滑动窗口最小值查询，将时间复杂度降为O(n)。 详细步骤 计算前缀和 构建前缀和数组 prefix ，其中 prefix[0] = 0 ， prefix[i] = nums[0] + nums[1] + ... + nums[i-1] 。 例如，对 nums = [1, -2, 3, 4, -1, 2] ，有 prefix = [0, 1, -1, 2, 6, 5, 7] 。 初始化队列和结果 使用双端队列 deque 存储候选前缀和索引，保证队列索引对应的前缀和递增。 初始化 max_sum = -∞ ，队列放入索引0（对应 prefix[0] = 0 ）。 滑动窗口遍历 遍历 j 从1到n（n为数组长度）： a. 移除过期索引 ：若队首索引 i 满足 j - i > L ，则出队（确保窗口长度≤L）。 b. 更新最大和 ：计算当前候选和 sum = prefix[j] - prefix[deque[0]] ，更新 max_sum 。 c. 维护队列单调性 ：从队尾移除所有满足 prefix[i] ≥ prefix[j] 的索引 i （因为后续j更优），再将j入队。 注意：先更新最大和，再维护队列，确保队列中总存在最小前缀和。 举例说明 以 nums = [1, -2, 3, 4, -1, 2] , L=3 为例： j=1: prefix[ 1]=1, 队列[ 0], 和=1-0=1, max_ sum=1 j=2: prefix[ 2]=-1, 队列[ 0,2]（移除1? 不，prefix[ 1 ]=1 > -1? 先算和：和=-1-0=-1；再维护队列：队尾1的prefix=1 > -1? 是，所以移除1，加入2） j=3: prefix[ 3]=2, 队列[ 0,2], 和=2-(-1)=3, max_ sum=3 j=4: prefix[ 4]=6, 队列[ 2,3]（j=4时，检查队首0：4-0=4>L=3，移除0），和=6-(-1)=7, max_ sum=7 j=5: prefix[ 5]=5, 队列[ 2,3,5]? 先算和：5-(-1)=6；再维护：队尾3的prefix=2 <5，直接加入5 j=6: prefix[ 6]=7, 队列[ 3,5,6]? 先算和：7-2=5；维护：队尾5的prefix=5 <7，加入6 最终最大和为7（对应子数组[ 3,4]或[ 3,4,-1]？实际是[ 3,4 ]：索引3到4，和=3+4=7）。 复杂度分析 时间复杂度：O(n)，每个元素入队出队一次。 空间复杂度：O(n)，用于存储前缀和和队列。 核心技巧 将子数组和问题转化为前缀和差分问题。 用单调队列高效维护滑动窗口最小值，避免重复计算。