带限制条件的最大子数组和问题 题目描述 给定一个整数数组nums和一个整数k，要求找到最大子数组和，但是有一个限制条件：子数组中不能包含长度大于等于k的连续负数段。也就是说，在选择的子数组中，如果出现负数，那么连续负数的长度必须小于k。 解题思路 这个问题是最大子数组和问题的变种，增加了对连续负数段长度的限制。我们需要在动态规划状态中记录当前连续负数的长度，以便判断是否满足限制条件。 详细解题步骤 状态定义 定义dp[ i ]表示以第i个元素结尾的满足条件的子数组的最大和。 同时，我们需要一个辅助状态neg_ len[ i ]记录以第i个元素结尾的子数组中，当前连续负数的长度。 状态转移方程 对于每个位置i，我们需要考虑两种情况： 如果nums[ i ] ≥ 0： dp[ i] = max(nums[ i], dp[ i-1] + nums[ i ]) neg_ len[ i ] = 0（因为当前是正数，连续负数长度重置为0） 如果nums[ i] < 0： 如果neg_ len[ i-1] < k-1（即加上当前负数后连续负数长度仍小于k）： dp[ i] = max(nums[ i], dp[ i-1] + nums[ i ]) neg_ len[ i] = neg_ len[ i-1 ] + 1 否则（连续负数长度将达到k，违反限制）： 我们需要向前找到第一个不是连续负数的位置，重新开始计算 边界条件 当i=0时（第一个元素）： dp[ 0] = nums[ 0 ] neg_ len[ 0] = 1 if nums[ 0] < 0 else 0 算法实现细节 实际上，我们需要更细致地处理当连续负数长度达到k时的情况。这时候不能简单地取nums[ i ]自己，因为可能前面有更优的解。 更完整的状态设计 我们可以设计一个二维DP： dp[ i][ j ]：表示以第i个元素结尾，且当前连续负数长度为j的子数组的最大和 其中0 ≤ j < k 状态转移： 如果nums[ i ] ≥ 0： dp[ i][ 0] = max(nums[ i], dp[ i-1][ j] + nums[ i ]) 对于所有j 其他dp[ i][ j ] = -∞（因为正数会重置连续负数计数） 如果nums[ i] < 0： 对于j > 0：dp[ i][ j] = dp[ i-1][ j-1] + nums[ i ] dp[ i][ 1]还要考虑从当前位置重新开始：max(dp[ i][ 1], nums[ i ]) 最终答案 max{dp[ i][ j]} 对于所有i和0 ≤ j < k 示例演示 假设nums = [ 2, -1, 3, -2, -3, 4 ]，k = 2 执行过程： i=0: num=2≥0, dp[ 0][ 0 ]=2 i=1: num=-1<0, dp[ 1][ 1 ]=max(2-1, -1)=1 i=2: num=3≥0, dp[ 2][ 0 ]=max(3, 1+3)=4 i=3: num=-2<0, dp[ 3][ 1 ]=max(4-2, -2)=2 i=4: num=-3 <0 连续负数长度将达2（等于k），需要特殊处理 只能从i=3重新开始：dp[ 4][ 1 ]=-3 或者包含前面但不超过限制：dp[ 4][ 2 ]不合法 i=5: num=4≥0, dp[ 5][ 0 ]=max(4, -3+4)=1 最大值为4（子数组[ 2, -1, 3 ]） 复杂度分析 时间复杂度：O(nk)，其中n为数组长度 空间复杂度：O(nk)，可优化到O(k) 这个解法通过二维DP精确跟踪了连续负数的长度，确保在任何时候都不违反题目限制条件。