带限制条件的最大子数组和（限制子数组必须包含至少K个元素） 题目描述： 给定一个整数数组 nums 和一个整数 K （K ≥ 1），要求找到一个长度 至少为 K 的连续子数组，使得这个子数组的和最大。 例如：nums = [ 2, 1, -3, 4, -1, 2, 1, -5, 4 ]，K = 3。 长度为 3 以上的子数组中，[ 4, -1, 2, 1 ] 和为 6 是最大，长度为 4 ≥ K=3。 目标是设计一个线性动态规划算法，时间复杂度 O(n)。 解题过程： 步骤 1：问题理解 普通的最大子数组和（Kadane算法）不限制长度，而这里要求子数组长度至少为 K。 这意味着我们不能简单地用 dp[i] 表示以 i 结尾的最大和子数组，因为那样可能会选择长度为 1 的子数组，不一定满足 ≥K 的条件。 我们需要将“长度至少 K”这个约束融入状态设计。 步骤 2：状态设计 定义两个状态数组，长度 n： sum[i] 表示前 i 个元素的和（前缀和）， sum[i] = nums[0] + ... + nums[i-1] ， sum[0] = 0 。 我们需要考虑以 i 结尾、长度至少为 K 的子数组的最大和。 设 dp[i] 表示以第 i 个元素 结尾 、长度 至少为 K 的连续子数组的最大和。 注意：这里“至少为 K”意味着子数组可以是 K, K+1, …, 直到 i+1（如果 i 从0编号的话，以 i 结尾的子数组长度最大为 i+1）。 但我们更直接的方法是： 先计算固定长度为 K 的子数组的和，再考虑扩展。 用动态规划的思想：以 i 结尾的长度 ≥K 的子数组，可以拆分为两部分：一个长度刚好为 K 的段（从 i-K+1 到 i），再加上前面可能的一段（但前面那段必须以 i-K 结尾，且长度任意）。 步骤 3：状态转移推导 设前缀和 prefix[i] 表示前 i 个元素的和（i 从 0 到 n，prefix[ 0 ]=0）。 对于以 i 结尾、长度 ≥K 的子数组： 如果长度刚好是 K，和 = prefix[i+1] - prefix[i+1-K] 。 如果长度大于 K，那么可以看作以 i-1 结尾、长度 ≥K 的子数组，再追加 nums[ i ]。 但这样不对，因为长度 ≥K 的子数组必须保证起点在 i-K+1 或更前。 更严谨的推导： 以 i 结尾的长度 ≥K 的子数组 = 从某个 j 到 i，且 i-j+1 ≥ K，即 j ≤ i-K+1。 我们想找这些 j 中，使得 sum(nums[ j..i ]) 最大的 j。 sum(nums[ j..i]) = prefix[ i+1] - prefix[ j ]。 所以要最大化 prefix[ i+1] - prefix[ j ]，其中 j ≤ i-K+1。 等价于固定 i 时，在 j 的取值范围 [ 0, i-K+1] 中找到最小的 prefix[ j ]。 设 minPrefix[j] 表示 prefix[ 0..j] 的最小值，那么对于 i，最小前缀和可以在 j ≤ i-K+1 时得到，为 minPrefix[i-K+1] 。 那么最大子数组和候选 = prefix[i+1] - minPrefix[i-K+1] 。 但这里有一个问题：这样找到的子数组长度可能是从 0 到 i-K+1 的任意长度，但我们要的是长度 ≥K，即 j 必须 ≤ i-K+1 且长度 i-j+1 ≥K 是自动满足的（因为 j ≤ i-K+1 意味着长度至少 K）。 但我们需要比较不同 i 的候选值。 实际上，更简单的动态规划： 定义 dp[i] 表示以 i 结尾的长度 ≥K 的子数组的最大和。 那么： 如果取长度刚好为 K 的子数组，和为 prefix[i+1] - prefix[i+1-K] 。 如果长度大于 K，那么它一定是以 i-1 结尾的长度 ≥K 的子数组加上 nums[ i]，即 dp[i-1] + nums[i] 。 因为以 i-1 结尾的长度 ≥K 的子数组，再追加 nums[ i ] 后长度一定 ≥K+1，满足条件。 所以 dp[i] = max(prefix[i+1] - prefix[i+1-K], dp[i-1] + nums[i]) 。 步骤 4：初始化和边界 对于 i = K-1（0-based index），它是第一个可能的长度 ≥K 的子数组的结尾。 此时 dp[ K-1] 只能是长度为 K 的子数组，即 prefix[K] - prefix[0] 。 对于 i < K-1，dp[ i ] 不存在（因为长度不够 K），我们可以忽略或设为 -∞。 从 i = K 开始，就可以用递推式了。 步骤 5：最终答案 最终答案是所有 dp[i] 中的最大值，i 从 K-1 到 n-1。 步骤 6：例子验证 nums = [ 2, 1, -3, 4, -1, 2, 1, -5, 4 ]，K=3。 前缀和 prefix = [ 0, 2, 3, 0, 4, 3, 5, 6, 1, 5 ]。 i=2: dp[ 2] = prefix[ 3]-prefix[ 0 ] = 0-0=0。 i=3: prefix[ 4]-prefix[ 1] = 4-2=2，dp[ 2]+nums[ 3 ] = 0+4=4，max=4。 i=4: prefix[ 5]-prefix[ 2] = 3-3=0，dp[ 3]+nums[ 4 ]=4+(-1)=3，max=3。 i=5: prefix[ 6]-prefix[ 3]=5-0=5，dp[ 4]+nums[ 5 ]=3+2=5，max=5。 i=6: prefix[ 7]-prefix[ 4]=6-4=2，dp[ 5]+nums[ 6 ]=5+1=6，max=6。 i=7: prefix[ 8]-prefix[ 5]=1-3=-2，dp[ 6]+nums[ 7 ]=6+(-5)=1，max=1。 i=8: prefix[ 9]-prefix[ 6]=5-5=0，dp[ 7]+nums[ 8 ]=1+4=5，max=5。 max(dp[ 2..8]) = 6，对应的子数组是 [ 4, -1, 2, 1 ]，长度 4，和 6，正确。 步骤 7：复杂度分析 计算前缀和 O(n)，然后递推 dp 从 K-1 到 n-1 也是 O(n)，空间 O(n) 可优化为 O(1) 只保存 dp[ i-1 ] 和 prefix 数组（其实可以只保存一个最小前缀和变量）。 步骤 8：优化空间 我们可以不用显式的 dp 数组，用一个变量 curMax 记录当前 dp[ i ]，然后不断更新答案。 但注意递推式需要前缀和，我们可以用变量记录 prefix[i-K] 的最小值来直接求长度刚好 K 的情况，但递推式中 dp[i-1] + nums[i] 需要前一状态，所以还是保留一个变量记录前一个状态的 dp 值即可。 实际上，更简洁的实现是： 用变量 sumK 记录当前连续 K 个数的和（滑动窗口）。 用变量 maxSum 记录最终答案。 用变量 maxSumEndingAt 记录以当前下标结尾的长度 ≥K 的子数组的最大和（即 dp[ i ]）。 初始化： sumK 为前 K 个数的和， maxSumEndingAt = sumK ， maxSum = sumK 。 从 i=K 到 n-1： 更新 sumK += nums[i] - nums[i-K] （保持最新 K 个数的和）。 maxSumEndingAt = max(sumK, maxSumEndingAt + nums[i]) 。 maxSum = max(maxSum, maxSumEndingAt) 。 最后返回 maxSum 。 这个优化后的方法更直观： sumK 是以 i 结尾的长度为 K 的子数组的和。 maxSumEndingAt 是以 i 结尾的长度 ≥K 的子数组的最大和，由“长度为 K”或“前一个 ≥K 的子数组加上当前数”得到。 最终算法步骤 ： 初始化 sumK 为 nums[ 0..K-1 ] 的和。 初始化 maxSumEndingAt = sumK ， maxSum = sumK 。 从 i=K 到 n-1： 更新 sumK += nums[i] - nums[i-K] 。 更新 maxSumEndingAt = max(sumK, maxSumEndingAt + nums[i]) 。 更新 maxSum = max(maxSum, maxSumEndingAt) 。 返回 maxSum 。 这样就在 O(n) 时间、O(1) 空间解决了问题。