带限制条件的最大子数组和问题

题目描述
给定一个整数数组nums，找到具有最大和的连续子数组（子数组最少包含一个元素），但是有一个限制条件：子数组中不能包含相邻的两个元素（这里的相邻指的是在原数组中的位置相邻）。返回这个最大和。

解题思路分析
这个问题是最大子数组和问题的变种，增加了"不能包含相邻元素"的限制条件。我们需要设计一个动态规划状态来记录包含当前元素和不包含当前元素两种情况下的最大和。

详细解题步骤

步骤1：定义状态
我们定义两个状态数组：

• dp_include[i]：表示考虑前i个元素，且选择第i个元素时的最大和
• dp_exclude[i]：表示考虑前i个元素，且不选择第i个元素时的最大和

步骤2：状态转移方程
对于每个位置i（从1开始计数）：

1. 如果选择第i个元素，那么第i-1个元素不能被选择：
   dp_include[i] = max(dp_exclude[i-1] + nums[i-1], nums[i-1])

2. 如果不选择第i个元素，那么最大和就是前i-1个元素的最大和：
   dp_exclude[i] = max(dp_include[i-1], dp_exclude[i-1])

步骤3：边界条件

• 当i=1时（第一个元素）：
  dp_include[1] = nums[0]
  dp_exclude[1] = 0

步骤4：计算过程示例
以数组nums = [3, 2, 7, 10]为例：

i=1（元素3）：

• dp_include[1] = 3
• dp_exclude[1] = 0
• 当前最大和 = max(3, 0) = 3

i=2（元素2）：

• dp_include[2] = max(dp_exclude[1] + 2, 2) = max(0+2, 2) = 2
• dp_exclude[2] = max(dp_include[1], dp_exclude[1]) = max(3, 0) = 3
• 当前最大和 = max(2, 3) = 3

i=3（元素7）：

• dp_include[3] = max(dp_exclude[2] + 7, 7) = max(3+7, 7) = 10
• dp_exclude[3] = max(dp_include[2], dp_exclude[2]) = max(2, 3) = 3
• 当前最大和 = max(10, 3) = 10

i=4（元素10）：

• dp_include[4] = max(dp_exclude[3] + 10, 10) = max(3+10, 10) = 13
• dp_exclude[4] = max(dp_include[3], dp_exclude[3]) = max(10, 3) = 10
• 最终结果 = max(13, 10) = 13

步骤5：空间优化
由于每个状态只依赖于前一个状态，我们可以用两个变量代替数组：

• include：包含当前元素的最大和
• exclude：不包含当前元素的最大和

优化后的代码实现：

def maxSubarraySumNoAdjacent(nums):
    if not nums:
        return 0
    
    include = nums[0]  # 包含第一个元素
    exclude = 0        # 不包含第一个元素
    
    for i in range(1, len(nums)):
        # 保存前一个include值
        prev_include = include
        
        # 更新include：要么是前一个exclude+当前元素，要么是当前元素本身
        include = max(exclude + nums[i], nums[i])
        
        # 更新exclude：前一个include和exclude的最大值
        exclude = max(prev_include, exclude)
    
    return max(include, exclude)

步骤6：复杂度分析

• 时间复杂度：O(n)，只需要遍历数组一次
• 空间复杂度：O(1)，只使用了常数级别的额外空间

这个算法巧妙地处理了"不能包含相邻元素"的限制条件，通过维护两个状态来分别记录包含和不包含当前元素的情况，确保了解决方案的最优性。