带限制条件的最大子数组和问题 题目描述 给定一个整数数组nums，找到具有最大和的连续子数组（子数组最少包含一个元素），但是有一个限制条件：子数组中不能包含相邻元素（即子数组中的元素在原数组中不能相邻）。返回这个最大和。 示例： 输入：nums = [ 1,2,3,4,5 ] 输出：9 解释：选择元素1,3,5（索引0,2,4），和为9。不能选择相邻元素2和4。 解题过程 这个问题是最大子数组和问题的变种，加入了"不能包含相邻元素"的限制条件。我们需要使用动态规划来记录不同状态下的最优解。 步骤1：定义状态 我们定义dp[ i ]表示考虑前i个元素（从0到i-1）时，能够获得的最大和，并且满足不包含相邻元素的限制。 但是这里需要注意，由于不能包含相邻元素，当我们考虑第i个元素时，有两种选择： 选择当前元素nums[ i ]，那么就不能选择前一个元素i-1 不选择当前元素，那么可以选择前一个元素 因此我们需要更精细的状态定义： dp[ i][ 0 ]：考虑前i个元素，不选择第i个元素时的最大和 dp[ i][ 1 ]：考虑前i个元素，选择第i个元素时的最大和 步骤2：状态转移方程 对于每个位置i（从0开始）： 如果不选择第i个元素（dp[ i][ 0 ]）： 那么前i-1个元素可以选择也可以不选择第i-1个元素 dp[ i][ 0] = max(dp[ i-1][ 0], dp[ i-1][ 1 ]) 如果选择第i个元素（dp[ i][ 1 ]）： 那么第i-1个元素一定不能选择 只能从前i-1个元素中不选择第i-1个元素的状态转移过来 dp[ i][ 1] = dp[ i-1][ 0] + nums[ i ] 步骤3：边界条件 当i=0时（第一个元素）： dp[ 0][ 0 ] = 0（不选择第一个元素，和为0） dp[ 0][ 1] = nums[ 0 ]（选择第一个元素） 步骤4：计算顺序 从i=1开始，依次计算到i=n-1（n为数组长度） 步骤5：最终结果 最终结果是max(dp[ n-1][ 0], dp[ n-1][ 1 ]) 具体示例分析 以nums = [ 1,2,3,4,5 ]为例： i=0（元素1）： dp[ 0][ 0 ] = 0 dp[ 0][ 1 ] = 1 i=1（元素2）： dp[ 1][ 0] = max(dp[ 0][ 0], dp[ 0][ 1 ]) = max(0,1) = 1 dp[ 1][ 1] = dp[ 0][ 0 ] + 2 = 0 + 2 = 2 i=2（元素3）： dp[ 2][ 0] = max(dp[ 1][ 0], dp[ 1][ 1 ]) = max(1,2) = 2 dp[ 2][ 1] = dp[ 1][ 0 ] + 3 = 1 + 3 = 4 i=3（元素4）： dp[ 3][ 0] = max(dp[ 2][ 0], dp[ 2][ 1 ]) = max(2,4) = 4 dp[ 3][ 1] = dp[ 2][ 0 ] + 4 = 2 + 4 = 6 i=4（元素5）： dp[ 4][ 0] = max(dp[ 3][ 0], dp[ 3][ 1 ]) = max(4,6) = 6 dp[ 4][ 1] = dp[ 3][ 0 ] + 5 = 4 + 5 = 9 最终结果：max(6,9) = 9 优化空间复杂度 由于dp[ i]只依赖于dp[ i-1 ]，我们可以用两个变量代替整个dp数组： prev0：前一个位置不选择的最大和 prev1：前一个位置选择的最大和 这样可以将空间复杂度从O(n)优化到O(1)。