求长度≤k的非连续非重叠子数组最大和的时间优化方法

解法思路 #

这是打家劫舍问题的扩展，核心是通过动态规划+单调队列优化将时间复杂度从O(nk)降至O(n)，适配1e5规模的数据：

1. 状态定义：设dp[i]表示考虑前i个元素（即arr[0..i-1]）的最大和。
2. 状态转移：
   • 不选包含arr[i-1]的子数组：dp[i] = dp[i-1]
   • 选包含arr[i-1]的子数组：需选择一个以arr[i-1]结尾、长度l∈[1,k]的子数组arr[i-l..i-1]，此时前面的最大和为dp[i-l-1]（保证子数组不重叠不连续）。利用前缀和pre简化求和后，总和可改写为pre[i] + (dp[i-l-1] - pre[i-l])。
   • 最终状态转移式：dp[i] = max(dp[i-1], pre[i] + max{ dp[m] - pre[m+1] | m ∈ [max(-1, i-k-1), i-2] })，其中m = i-l-1对应所有合法子数组长度。
3. 单调队列优化：用单调递减队列维护窗口内dp[m]-pre[m+1]的最大值，每个元素仅入队出队一次，保证线性时间复杂度。

具体步骤 #

1. 计算前缀和：pre[0] = 0，pre[i] = pre[i-1] + arr[i-1]（i从1到数组长度n）。
2. 初始化DP数组：dp[0] = 0，dp[1] = max(0, arr[0])（k≥1，可选择第一个元素或不选）。
3. 初始化单调队列：将m=-1（对应dp[-1]=0）和m=0加入队列，维护队列中元素对应的dp[m]-pre[m+1]单调递减。
4. 遍历计算DP：
   • 对每个i从2到n：
     • 移除队列中不在窗口[max(-1, i-k-1), i-2]的元素（队首元素小于窗口左边界则弹出）。
     • 取队首元素对应的最大值val_max，计算候选值pre[i] + val_max。
     • dp[i] = max(dp[i-1], 候选值)。
     • 计算当前m=i-1对应的val = dp[i-1] - pre[i]，弹出队列中所有val小于等于当前val的元素（它们无法成为后续窗口的最大值），将m=i-1加入队列。
5. 最终结果：dp[n]即为答案。

代码实现（Python） #

from collections import deque

def max_sum(arr, k):
    n = len(arr)
    if n == 0:
        return 0
    # 前缀和数组
    pre = [0] * (n + 1)
    for i in range(1, n + 1):
        pre[i] = pre[i-1] + arr[i-1]
    
    dp = [0] * (n + 1)
    dp[1] = max(0, arr[0])
    
    # 单调队列，存储m值，对应dp[m]-pre[m+1]单调递减
    q = deque()
    q.append(-1)
    q.append(0)
    
    for i in range(2, n + 1):
        left = max(-1, i - k - 1)
        # 移除窗口外的元素
        while q and q[0] < left:
            q.popleft()
        
        # 计算当前候选值
        if q:
            m = q[0]
            val_max = 0 - pre[0] if m == -1 else dp[m] - pre[m+1]
            candidate = pre[i] + val_max
        else:
            candidate = pre[i]
        
        dp[i] = max(dp[i-1], candidate)
        
        # 加入当前m=i-1到队列
        current_val = dp[i-1] - pre[i]
        while q:
            last_m = q[-1]
            last_val = 0 - pre[0] if last_m == -1 else dp[last_m] - pre[last_m+1]
            if last_val <= current_val:
                q.pop()
            else:
                break
        q.append(i-1)
    
    return dp[n]

# 示例测试
arr1 = [1,10,7,3,4]
k1 = 1
print(max_sum(arr1, k1))  # 输出14

arr2 = [15,9,11,11,1,12,18,18,18,8,1]
k2 = 3
print(max_sum(arr2, k2))  # 输出94

复杂度分析 #

• 时间复杂度：O(n)，前缀和计算、DP遍历均为线性，单调队列每个元素仅入队出队一次。
• 空间复杂度：O(n)，需存储前缀和数组和DP数组，队列最多存储O(k)个元素，整体为线性空间。

内容的提问来源于stack exchange，提问作者Shirina