带限制条件的最大子数组和（限制子数组长度不超过L） 题目描述 给定一个整数数组 nums 和一个正整数 L ，要求找到一个长度 不超过 L 的连续子数组，使得该子数组的和最大。返回这个最大和。 例如： 输入： nums = [1, -2, 3, 4, -1, 2] , L = 3 输出： 7 （对应子数组 [3, 4, -1, 2] 中长度不超过3的最大和子数组为 [3, 4] ，和为7） 解题过程 步骤1：理解问题核心 普通的最大子数组和问题（Kadane算法）不限制子数组长度，但本题要求子数组长度不超过 L 。这意味着我们需要在所有长度 ≤ L 的连续子数组中找出和最大的那个。 步骤2：暴力法的局限性 直接枚举所有长度 ≤ L 的子数组，计算它们的和，然后取最大值。时间复杂度为 O(nL)，当 n 和 L 都很大时效率低。 步骤3：动态规划思路 定义 dp[i] 为以第 i 个元素结尾的、长度不超过 L 的最大子数组和。但直接这样定义会遇到问题：因为长度限制 L 是全局的，我们需要快速计算任意结尾的子数组的和。 步骤4：前缀和与滑动窗口 计算前缀和数组 prefix ，其中 prefix[i] 表示前 i 个元素的和（ prefix[0] = 0 ， prefix[i] = nums[0] + ... + nums[i-1] ）。 对于以 i 结尾的子数组，其和可以表示为 prefix[i+1] - prefix[j] ，其中 j 是子数组起始位置的前一个索引，且满足 i - j ≤ L 。 问题转化为：对于每个 i，找到 j 在 [i-L, i] 范围内，使得 prefix[j] 最小，这样 prefix[i+1] - prefix[j] 最大。 步骤5：使用单调队列优化 维护一个单调递增队列（队首到队尾递增），存储 prefix 数组的索引。 遍历 i 从 0 到 n-1： 确保队列中的索引在 [i-L, i] 范围内（超出范围则出队）。 当前最大候选和为 prefix[i+1] - prefix[queue.front()] 。 将 i 加入队列前，弹出所有 prefix[j] ≥ prefix[i] 的 j （因为这些 j 不会成为未来更优的选择）。 步骤6：算法步骤详解 初始化 prefix[0] = 0 ， maxSum = -∞ ，单调队列 dq 为空。 遍历 i 从 0 到 n-1： prefix[i+1] = prefix[i] + nums[i] 如果 dq 非空且队首索引 < i-L+1 ，则出队队首（因为子数组长度不能超过 L）。 更新 maxSum = max(maxSum, prefix[i+1] - prefix[dq.front()]) 维护单调队列：从队尾弹出所有 prefix[j] ≥ prefix[i+1] 的 j，然后将 i+1 加入队尾。 返回 maxSum 。 步骤7：示例演算 nums = [1, -2, 3, 4, -1, 2] , L = 3 prefix = [0, 1, -1, 2, 6, 5, 7] i=0: dq=[ 0 ], maxSum=1-0=1 i=1: dq=[ 0,1]（prefix[ 1]=-1 <0，保留）, maxSum=max(1, -1-0)=-1? 错误！应检查范围：i=1，允许 j 从 max(0,1-3+1)=0 到 1，最优 j=0 → maxSum=1 正确流程： i=0: dq=[ 0], 候选=prefix[ 1]-prefix[ 0 ]=1 i=1: 队首0在范围内，候选=prefix[ 2]-prefix[ 0 ]=-1；加入索引2前弹出1? 需注意索引范围。 实际执行需严格按步骤5。最终得到最大和7（i=3时，prefix[ 4]-prefix[ 2 ]=6-(-1)=7）。 步骤8：复杂度分析 时间复杂度：O(n)，每个元素入队出队一次。 空间复杂度：O(n)，用于前缀和和队列。 通过以上步骤，我们高效地解决了带长度限制的最大子数组和问题。