线性动态规划：带限制的最大子数组和（限制子数组长度不超过L） 题目描述 给定一个整数数组 nums 和一个正整数 L ，要求找到一个长度 不超过 L 的连续子数组，使得该子数组的和最大。返回这个最大和。 示例 输入： nums = [3, 1, -4, 2, 8, -1, 6], L = 3 输出： 10 （子数组 [2, 8] 或 [2, 8, -1, 6] 中长度不超过3的最大和是 [2, 8] 的和10，但注意 [2, 8, -1, 6] 长度超过3，不符合条件） 解题过程 步骤1：理解问题核心 这是最大子数组和问题（Kadane算法）的变种，但增加了子数组长度不超过 L 的限制。 直接应用Kadane算法会忽略长度限制，可能得到长度超过 L 的子数组。 需要确保在计算过程中，只考虑长度在 L 以内的窗口。 步骤2：暴力法的局限性 枚举所有长度不超过 L 的子数组，计算它们的和，取最大值。 时间复杂度：O(n²)，对于大规模数组效率低。 优化目标：将复杂度降至 O(n) 或 O(n log n)。 步骤3：动态规划思路 定义 dp[i] 为以第 i 个元素结尾的、长度不超过 L 的子数组的最大和。 状态转移时，需考虑两种情况： 单独以 nums[i] 作为子数组： nums[i] 。 将 nums[i] 接在以 i-1 结尾的子数组之后，但需确保接上后长度不超过 L 。 但直接递推会重复计算区间和，且难以控制长度。 步骤4：前缀和+滑动窗口优化 使用前缀和数组 prefix ，其中 prefix[i] 表示 nums[0..i-1] 的和（ prefix[0]=0 ）。 子数组 nums[j..i] 的和 = prefix[i+1] - prefix[j] ，其中 i - j ≤ L 。 问题转化为：对每个 i ，在区间 [max(0, i-L+1), i] 中找最小的 prefix[j] ，使 prefix[i+1] - prefix[j] 最大。 这等价于用滑动窗口维护当前窗口内最小的 prefix[j] 。 步骤5：算法步骤 计算前缀和数组 prefix 。 使用双端队列 deque 维护一个宽度为 L 的滑动窗口，存储下标 j ，保证队首的 prefix[j] 最小。 遍历 i 从 0 到 n-1 ： 移除队首超出窗口范围的下标（ j < i - L + 1 ）。 当前最大和候选值 = prefix[i+1] - prefix[deque.front()] 。 从队尾移除比 prefix[i+1] 大的值（保证队列单调递增）。 将 i+1 加入队尾（因为下次计算会用 prefix[i+1] 作为减数）。 遍历过程中记录最大和。 步骤6：示例推导 nums = [3, 1, -4, 2, 8, -1, 6], L=3 前缀和 prefix = [0, 3, 4, 0, 2, 10, 9, 15] i=0 ：窗口 [ 0,0 ]，队列存0，候选和=3-0=3。 i=1 ：窗口 [ 0,1 ]，队列存0,1，候选和=4-0=4。 i=2 ：窗口 [ 0,2]，队列存0,2（移除1因prefix[ 1]=3>prefix[ 2 ]=0），候选和=0-0=0。 i=3 ：窗口 [ 1,3 ]，队列存2,3，候选和=2-0=2。 i=4 ：窗口 [ 2,4]，队列存2,4（移除3因prefix[ 3]=2>prefix[ 4]=10无意义，但队列存最小prefix[ 2 ]=0），候选和=10-0=10（更新最大值）。 继续遍历得最大和10。 步骤7：复杂度分析 时间复杂度：O(n)，每个元素入队出队一次。 空间复杂度：O(n)（前缀和数组和队列）。 总结 通过结合前缀和与单调队列，可在O(n)时间内解决带长度限制的最大子数组和问题。关键在于将问题转化为寻找滑动窗口内的最小前缀和，从而快速计算最大区间和。