最大子数组和问题的变种——至少包含一个特定元素的最大子数组和

字数 2802 2025-12-17 07:37:27

最大子数组和问题的变种——至少包含一个特定元素的最大子数组和

问题描述

给定一个整数数组 nums 和一个整数 target。你需要找到一个连续子数组，使得该子数组的和最大，并且该子数组必须至少包含一个值为 target 的元素。如果数组中不存在 target，则返回 0。

例如：

输入：nums = [1, -2, 3, 4, -1, 2], target = 3
输出：8
解释：包含 3 的最大和连续子数组是 [3, 4, -1, 2]，和为 8。
输入：nums = [5, -1, -2, 3, -4], target = 3
输出：3
解释：包含 3 的最大和连续子数组就是 [3]，和为 3。

解题思路

这是一个最大子数组和问题的变种，额外约束是子数组必须至少包含一个特定元素 target。我们将问题分解为以每个位置 i 为结尾考虑，并记录两种状态：

dp1[i]：表示以 nums[i] 结尾的、且必须包含至少一个 target 的连续子数组的最大和。
dp0[i]：表示以 nums[i] 结尾的、且不包含任何 target 的连续子数组的最大和。

为什么需要两个状态？因为约束是“至少包含一个 target”，我们可以从“不含 target”的状态在遇到 target 时转移到“包含 target”的状态。

状态转移分析

对于每个位置 i，考虑 nums[i] 的值：

如果 nums[i] == target：
- 对于 dp1[i]（必须包含 target）：
  - 可以从前面已包含 target 的子数组接上来：dp1[i-1] + nums[i]
  - 或者从前面不含 target 的子数组接上来（现在遇到了 target，所以变成包含 target）：dp0[i-1] + nums[i]
  - 或者只取当前元素 nums[i] 自己作为一个新的子数组。
  - 因此，dp1[i] = max(dp1[i-1] + nums[i], dp0[i-1] + nums[i], nums[i])。
- 对于 dp0[i]（不含 target）：
  - 因为当前元素就是 target，所以任何以 i 结尾且不含 target 的子数组都不存在，因此 dp0[i] = -∞（可以用一个极小值表示，因为后续不会从这个状态转移）。
如果 nums[i] != target：
- 对于 dp1[i]（必须包含 target）：
  - 必须从前面已包含 target 的子数组接上来：dp1[i-1] + nums[i]
  - 或者只取当前元素？不行，因为当前不是 target，单独取它不满足条件，所以不能只取 nums[i]。
  - 因此，dp1[i] = dp1[i-1] + nums[i]，但要注意如果 dp1[i-1] 不存在（为 -∞），那么 dp1[i] 也为 -∞。
- 对于 dp0[i]（不含 target）：
  - 可以从前面不含 target 的子数组接上来：dp0[i-1] + nums[i]
  - 或者只取当前元素自己：nums[i]
  - 因此，dp0[i] = max(dp0[i-1] + nums[i], nums[i])。

最终答案就是在所有 dp1[i] 中取最大值。

边界条件与初始化

在 i=0 时：
- 如果 nums[0] == target：
  - dp1[0] = nums[0]
  - dp0[0] = -∞
- 如果 nums[0] != target：
  - dp1[0] = -∞（因为单独一个非 target 元素不满足条件）
  - dp0[0] = nums[0]
我们可以用 -inf 表示不可能的状态，在代码中可以用一个很小的负数（如 -10^9）代替，或者单独处理。

逐步计算示例

以 nums = [1, -2, 3, 4, -1, 2], target = 3 为例：

i	nums[i]	dp0[i] (不含3)	dp1[i] (必须含3)
0	1	1 (只取自己)	-∞ (不可能)
1	-2	max(1 + (-2), -2) = -1	-∞ (仍不可能)
2	3	-∞ (因为当前是3，不含3不可能)	max(-∞+3, -1+3, 3) = 3
3	4	max(-∞+4, 4) = 4 (但注意：dp0[3]实际不会被后续用于dp1，因为已遇到3)	dp1[2] + 4 = 3 + 4 = 7
4	-1	max(4 + (-1), -1) = 3	dp1[3] + (-1) = 7 + (-1) = 6
5	2	max(3 + 2, 2) = 5	dp1[4] + 2 = 6 + 2 = 8

最终答案：max(dp1[i]) = max(3, 7, 6, 8) = 8。

算法实现

我们可以用两个变量 dp0 和 dp1 滚动更新，而不需要整个数组。

def maxSubarrayWithTarget(nums, target):
    INF = -10**9
    dp0 = INF  # 不含target的最大和
    dp1 = INF  # 必须含target的最大和
    ans = 0
    
    for x in nums:
        if x == target:
            # 新的dp1: 从含target的来，或不含target的来，或自己开始
            new_dp1 = max(dp1 + x, dp0 + x, x)
            # 新的dp0: 不可能
            new_dp0 = INF
        else:
            # 新的dp1: 只能从含target的来
            new_dp1 = dp1 + x if dp1 != INF else INF
            # 新的dp0: 从不含target的来，或自己开始
            new_dp0 = max(dp0 + x, x)
        
        dp0, dp1 = new_dp0, new_dp1
        if dp1 != INF:
            ans = max(ans, dp1)
    
    return ans

复杂度分析

时间复杂度：O(n)，遍历数组一次。
空间复杂度：O(1)，只用了常数个变量。

总结

这个问题通过维护两个状态（包含 target 和不包含 target）来满足约束条件，是最大子数组和问题的一种常见变种。关键在于理清状态转移，特别是当遇到 target 时，可以从“不含”状态转移到“包含”状态。

最大子数组和问题的变种——至少包含一个特定元素的最大子数组和问题描述给定一个整数数组 nums 和一个整数 target 。你需要找到一个连续子数组，使得该子数组的和最大，并且该子数组必须至少包含一个值为 target 的元素。如果数组中不存在 target ，则返回 0 。例如：输入： nums = [1, -2, 3, 4, -1, 2] , target = 3 输出： 8 解释：包含 3 的最大和连续子数组是 [3, 4, -1, 2] ，和为 8 。输入： nums = [5, -1, -2, 3, -4] , target = 3 输出： 3 解释：包含 3 的最大和连续子数组就是 [3] ，和为 3 。解题思路这是一个最大子数组和问题的变种，额外约束是子数组必须至少包含一个特定元素 target 。我们将问题分解为以每个位置 i 为结尾考虑，并记录两种状态： dp1[i] ：表示以 nums[i] 结尾的、且必须包含至少一个 target 的连续子数组的最大和。 dp0[i] ：表示以 nums[i] 结尾的、且不包含任何 target 的连续子数组的最大和。为什么需要两个状态？因为约束是“至少包含一个 target ”，我们可以从“不含 target ”的状态在遇到 target 时转移到“包含 target ”的状态。状态转移分析对于每个位置 i ，考虑 nums[i] 的值：如果 nums[i] == target ：对于 dp1[i] （必须包含 target ）：可以从前面已包含 target 的子数组接上来： dp1[i-1] + nums[i] 或者从前面不含 target 的子数组接上来（现在遇到了 target ，所以变成包含 target ）： dp0[i-1] + nums[i] 或者只取当前元素 nums[i] 自己作为一个新的子数组。因此， dp1[i] = max(dp1[i-1] + nums[i], dp0[i-1] + nums[i], nums[i]) 。对于 dp0[i] （不含 target ）：因为当前元素就是 target ，所以任何以 i 结尾且不含 target 的子数组都不存在，因此 dp0[i] = -∞ （可以用一个极小值表示，因为后续不会从这个状态转移）。如果 nums[i] != target ：对于 dp1[i] （必须包含 target ）：必须从前面已包含 target 的子数组接上来： dp1[i-1] + nums[i] 或者只取当前元素？不行，因为当前不是 target ，单独取它不满足条件，所以不能只取 nums[i] 。因此， dp1[i] = dp1[i-1] + nums[i] ，但要注意如果 dp1[i-1] 不存在（为 -∞ ），那么 dp1[i] 也为 -∞ 。对于 dp0[i] （不含 target ）：可以从前面不含 target 的子数组接上来： dp0[i-1] + nums[i] 或者只取当前元素自己： nums[i] 因此， dp0[i] = max(dp0[i-1] + nums[i], nums[i]) 。最终答案就是在所有 dp1[i] 中取最大值。边界条件与初始化在 i=0 时：如果 nums[0] == target ： dp1[0] = nums[0] dp0[0] = -∞ 如果 nums[0] != target ： dp1[0] = -∞ （因为单独一个非 target 元素不满足条件） dp0[0] = nums[0] 我们可以用 -inf 表示不可能的状态，在代码中可以用一个很小的负数（如 -10^9 ）代替，或者单独处理。逐步计算示例以 nums = [1, -2, 3, 4, -1, 2] , target = 3 为例： | i | nums[ i] | dp0[ i] (不含3) | dp1[ i ] (必须含3) | |---|---------|------------------------------------------|--------------------------------------------| | 0 | 1 | 1 (只取自己) | -∞ (不可能) | | 1 | -2 | max(1 + (-2), -2) = -1 | -∞ (仍不可能) | | 2 | 3 | -∞ (因为当前是3，不含3不可能) | max(-∞+3, -1+3, 3) = 3 | | 3 | 4 | max(-∞+4, 4) = 4 (但注意：dp0[ 3]实际不会被后续用于dp1，因为已遇到3) | dp1[ 2 ] + 4 = 3 + 4 = 7 | | 4 | -1 | max(4 + (-1), -1) = 3 | dp1[ 3 ] + (-1) = 7 + (-1) = 6 | | 5 | 2 | max(3 + 2, 2) = 5 | dp1[ 4 ] + 2 = 6 + 2 = 8 | 最终答案： max(dp1[i]) = max(3, 7, 6, 8) = 8 。算法实现我们可以用两个变量 dp0 和 dp1 滚动更新，而不需要整个数组。复杂度分析时间复杂度：O(n)，遍历数组一次。空间复杂度：O(1)，只用了常数个变量。总结这个问题通过维护两个状态（包含 target 和不包含 target ）来满足约束条件，是最大子数组和问题的一种常见变种。关键在于理清状态转移，特别是当遇到 target 时，可以从“不含”状态转移到“包含”状态。