🔥 个人主页: 黑洞晓威
😀你不必等到非常厉害，才敢开始，你需要开始，才会变的非常厉害。
摆动序列
1. 摆动序列定义
摆动序列是指连续数字之间的差严格地在正数和负数之间交替的数字序列。即，如果差值依次为正、负、正、负……则该序列为摆动序列。一个序列中仅有一个元素或者含有两个不等元素的序列也视作摆动序列。
2. 问题分析
给定一个整数数组 nums，要求找到 nums 中作为摆动序列的最长子序列的长度。换句话说，需要找到一个连续子序列，使得其中相邻元素的差值正负交替出现。
3. 解题思路
3.1. 动态规划
我们可以使用动态规划来解决这个问题。具体思路如下：
- 定义两个状态变量
up和down分别表示当前元素比前一个元素大或小的最长摆动序列长度。 - 遍历数组，对于每个元素，比较其与前一个元素的大小，更新
up和down的值。 - 最终返回
up和down中较大的值加 1，即为最长摆动序列的长度。
3.2. 贪心算法
贪心算法是另一种解决这个问题的方法。具体思路如下：
- 遍历数组，对于每个元素，计算与前一个元素的差值。
- 如果差值不为零，则与前一个差值的正负相反，更新当前摆动序列的长度。
- 如果差值为零，则不改变当前摆动序列的长度。
- 最终返回摆动序列的长度。
4. 具体实现
4.1. 动态规划实现
public int wiggleMaxLength(int[] nums) {
int n = nums.length;
if (n < 2) return n;
int up = 1, down = 1;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
} else if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return Math.max(up, down);
}
4.2. 贪心算法实现
public int wiggleMaxLength(int[] nums) {
int n = nums.length;
if (n < 2) return n;
int prevDiff = nums[1] - nums[0];
int count = prevDiff != 0 ? 2 : 1;
for (int i = 2; i < n; i++) {
int diff = nums[i] - nums[i - 1];
if ((diff > 0 && prevDiff <= 0) || (diff < 0 && prevDiff >= 0)) {
count++;
prevDiff = diff;
}
}
return count;
}
最大子序和
1. 最大子序和问题定义
给定一个整数数组 nums，要求找到一个具有最大和的连续子数组（子数组最少包含一个元素），并返回其最大和。
2. 问题分析
这是一个经典的动态规划问题。可以使用动态规划或者贪心算法来解决。
3. 解题思路
3.1. 动态规划
- 定义一个状态数组
dp，其中dp[i]表示以nums[i]结尾的最大子序和。 - 初始状态为
dp[0] = nums[0]。 - 对于每个位置
i，如果dp[i-1] > 0，则dp[i] = dp[i-1] + nums[i]；否则dp[i] = nums[i]。 - 最终结果即为
dp数组中的最大值。
3.2. 贪心算法
定义两个变量
maxSum和currSum，分别表示全局最大和和当前子数组的和。遍历数组
nums，对于每个元素：
- 更新
currSum = max(currSum + num, num)，表示要么继续加入当前元素，要么重新开始一个新的子数组。 - 更新
maxSum = max(maxSum, currSum)，表示更新全局最大和。
- 更新
最终返回
maxSum。
4. 具体实现
4.1. 动态规划实现
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
int maxSum = dp[0];
for (int i = 1; i < n; i++) {
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
maxSum = Math.max(maxSum, dp[i]);
}
return maxSum;
}
4.2. 贪心算法实现
public int maxSubArray(int[] nums) {
int maxSum = nums[0];
int currSum = nums[0];
for (int i = 1; i < nums.length; i++) {
currSum = Math.max(currSum + nums[i], nums[i]);
maxSum = Math.max(maxSum, currSum);
}
return maxSum;
}
