传媒公司属于什么行业类型_邯郸网站设计公司排名_青岛seo博客_网络营销seo培训

题目：最大非相邻子序列和

问题描述
给定一个长度为 n 的非负整数数组 nums，需从中选取若干个元素，使得选取的元素不相邻（即选取的元素在原数组中不能相邻），求选取元素的最大和。

示例
输入：nums = [2,7,9,3,1]
输出： 12
解释：选取第1、3、5个元素，总和为 2 + 9 + 1 = 12

---

解题思路

方法：动态规划

1. 状态定义
   定义 dp[i] 表示前 i 个元素中满足条件的最大和。

2. 状态转移

   • 若选择第 i 个元素，则不能选第 i-1 个元素，此时和为 dp[i-2] + nums[i]。
   • 若不选第 i 个元素，则和为 dp[i-1]。
   • 综上，转移方程为：

     dp[i]=max⁡(dp[i−1],dp[i−2]+nums[i])dp[i]=max(dp[i−1],dp[i−2]+nums[i])

3. 空间优化
   由于当前状态仅依赖前两个状态，可用变量 prevMax 和 currMax 代替数组，将空间复杂度优化至 O(1)O(1)。

---

public class MaxNonAdjacentSum {

public static int maxSum(int[] nums) {

if (nums == null || nums.length == 0)

return 0;

if (nums.length == 1)

return nums[0];

int prevMax = nums[0];

int currMax = Math.max(nums[0], nums[1]); for (int i = 2; i < nums.length; i++) {

int temp = currMax; currMax = Math.max(currMax, prevMax + nums[i]); prevMax = temp;

}

return currMax;

}

public static void main(String[] args) {

int[] nums = {2, 7, 9, 3, 1}; System.out.println(maxSum(nums));

// 输出 12

}

}

---

代码解析

1. 边界处理
   • 若数组为空，返回0；若长度为1，直接返回唯一元素。
2. 初始化
   • prevMax 表示前 i-2 个元素的最大和（初始为 nums[0]）。
   • currMax 表示前 i-1 个元素的最大和（初始为前两个元素的较大值）。
3. 状态更新
   遍历数组，每一步根据转移方程更新 currMax，并同步更新 prevMax。

通过动态规划思想，时间复杂度为 O(n)O(n)，空间复杂度为 O(1)O(1)，高效解决问题。