求满足和≥minSum且长度≥minLen的子数组最大数量技术求助

问题描述 #

给定一个数组，找出最多数量的不重叠连续子数组，每个子数组需满足两个条件：

1. 子数组的和 ≥ minSum
2. 子数组的长度 ≥ minLen

示例：

• 输入：数组=[5,7,9,12,10,13]，minLen=2，minSum=15
• 输出：2
• 解释：符合条件的不重叠子数组组合可以是[7,9,12]（和28）+[10,13]（和23），或者[7,9]（和16）+[12,10]（和22），两种组合的数量都是2，这是能达到的最大值。

解法思路 #

我们可以用动态规划+前缀和+二分查找的组合高效解决问题，核心逻辑如下：

1. 前缀和数组：快速计算任意子数组的和，避免重复计算。定义prefix[0] = 0，prefix[i]表示数组前i个元素的累加和（即arr[0]到arr[i-1]的和），子数组arr[j..k]的和可表示为prefix[k+1] - prefix[j]。
2. 动态规划数组：定义dp[i]为前i个元素中能选出的最大符合条件的子数组数量。dp数组单调不减，因为元素越多，可选的子数组数量不会减少。
3. 二分查找优化：对于每个位置i，找到最大的j（j ≤ i - minLen），使得prefix[j] ≤ prefix[i] - minSum（保证子数组arr[j..i-1]的和≥minSum）。利用dp的单调性，dp[i]可更新为max(dp[i-1], dp[j] + 1)。

代码实现（Python） #

def max_valid_subarrays(arr, minLen, minSum):
    n = len(arr)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + arr[i]
    
    dp = [0] * (n + 1)
    # 维护前缀和递增的候选列表，存储(prefix值, dp值, 原索引j)
    candidates = [(prefix[0], dp[0], 0)]
    
    for i in range(1, n+1):
        dp[i] = dp[i-1]
        target = prefix[i] - minSum
        max_j_allowed = i - minLen
        
        if max_j_allowed < 0:
            continue
        
        # 二分查找符合条件的最优j
        left, right = 0, len(candidates)-1
        best_idx = -1
        while left <= right:
            mid = (left + right) // 2
            if candidates[mid][0] <= target and candidates[mid][2] <= max_j_allowed:
                best_idx = mid
                left = mid + 1
            else:
                right = mid - 1
        
        if best_idx != -1:
            dp[i] = max(dp[i], candidates[best_idx][1] + 1)
        
        # 维护候选列表的前缀和递增性
        while candidates and candidates[-1][0] >= prefix[i]:
            candidates.pop()
        candidates.append((prefix[i], dp[i], i))
    
    return dp[n]

# 测试示例
arr = [5,7,9,12,10,13]
minLen = 2
minSum = 15
print(max_valid_subarrays(arr, minLen, minSum))  # 输出2

代码解释 #

1. 前缀和计算：构建前缀和数组，实现O(1)时间计算任意子数组的和。
2. 动态规划更新：dp[i]默认继承dp[i-1]（不选当前元素结尾的子数组），若找到符合条件的子数组，则更新为dp[j]+1。
3. 二分查找：在候选列表中快速定位最优的j，确保子数组满足长度和和的要求。
4. 候选列表维护：移除前缀和大于等于当前值的旧候选，保证列表前缀和递增，提升二分查找效率。

复杂度分析 #

• 时间复杂度：O(n log n)，每个元素最多被加入/移除候选列表一次，每次二分查找耗时O(log n)。
• 空间复杂度：O(n)，需存储前缀和数组、dp数组和候选列表。

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