难度适中，动态规划出现的比例还是比较高的，要好好掌握，二分查找的点也是比较灵活的。（A卷和B卷第一道题是一样的）
题目一：讨厌鬼的组合帖子
思路：这个题算是一个还不错的题；
本质就是：一个数组元素选或不选，可以达到的最大绝对值，经典动态规划入门题了，重要的就是能不能看到这个本质。
import java.util.Scanner;
public class taoTanGui {
public static void main(String[] args) {
// 创建 Scanner 对象用于读取输入
Scanner sc = new Scanner(System.in);
// 读取整数 n
int n = sc.nextInt();
// 创建长度为 n 的数组 a, b, c
long[] a = new long[n];
long[] b = new long[n];
long[] c = new long[n];
// 读取数组 a 的值
for (int i = 0; i < n; i++) {
a[i] = sc.nextLong();
}
// 读取数组 b 的值并计算 c[i] = a[i] - b[i]
for (int i = 0; i < n; i++) {
b[i] = sc.nextLong();
c[i] = a[i] - b[i];
}
// 创建二维 dp 数组，dp[i][0] 和 dp[i][1] 分别表示状态 i 的最小值和最大值
// i 表示 选1个，选2个，选3 个，选 4个
long[][] dp = new long[n + 1][2];
// 初始化 dp 数组中的所有元素为 0
// dp[0][0] = 0;
// dp[0][1] = 0;
// 计算 dp 数组
for (int i = 0; i < n; i++) {
// 选中当前元素的情况
dp[i + 1][0] = Math.min(dp[i][0], dp[i][1]) + c[i];
dp[i + 1][1] = Math.max(dp[i][0], dp[i][1]) + c[i];
// 不选当前元素的情况
dp[i + 1][0] = Math.min(dp[i][0], dp[i + 1][0]);
dp[i + 1][1] = Math.max(dp[i][1], dp[i + 1][1]);
}
// 计算最终结果（Math.abs()是取绝对值的api）
long ans = Math.max(Math.abs(dp[n][0]), Math.abs(dp[n][1]));
// 输出结果
System.out.println(ans);
// 关闭 Scanner 对象
sc.close();
}
}题目二：小红的16版方案
思路和代码
看到这种题，要有一个思想：二分查找，折半搜索最大的符合条件的版本号；
如何判断当前版本是否符合条件，可以使用 差分数组，其可以看错前缀和的逆过程，一定要掌握！
这段代码使用二分查找的思想，结合差分数组和前缀和的技巧来解决一个区间操作的最大化问题。通过逐步尝试更多的查询，找出能够满足条件的最大查询数量。
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取 n 和 m，n 表示数组 a 的长度，m 表示查询的数量
int n = sc.nextInt();
int m = sc.nextInt();
// 初始化数组 a，用于存储 n 个元素
long[] a = new long[n + 1];
for (int i = 1; i <= n; i++) {
a[i] = sc.nextLong(); // 读取数组 a 的值
}
// 创建二维数组 arr，用于存储 m 个查询，每个查询包含左右边界 l 和 r
List<int[]> arr = new ArrayList<>();
for (int i = 0; i < m; i++) {
int l = sc.nextInt();
int r = sc.nextInt();
arr.add(new int[] { l, r }); // 将每个查询的 [l, r] 存入列表
}
// 初始化左右边界 l 和 r，用于二分查找的范围
int l = 1;
int r = m;
// 二分查找，寻找最大的满足条件的 mid
while (l <= r) {
int mid = (l + r) / 2; // 计算中间值
// 创建数组 A，长度为 n + 2 用于差分数组的计算
int[] A = new int[n + 2];
// 根据当前 mid 值，应用前 mid 个查询，计算差分数组 A
for (int i = 0; i < mid; i++) {
int[] query = arr.get(i);
int aStart = query[0];
int aEnd = query[1];
A[aStart] += 1;
A[aEnd + 1] -= 1;
}
// 使用标志位 ok 来判断当前差分结果是否满足条件
boolean ok = true;
// 计算实际数组 A 中的每个值，判断是否超过数组 a 中对应位置的值
for (int i = 1; i <= n && ok; i++) {
A[i] += A[i - 1]; // 计算前缀和
if (A[i] > a[i]) {
ok = false; // 如果差分数组的值大于原数组 a 的值，则不满足条件
}
}
// 根据 ok 的结果调整二分查找的上下界
if (ok) {
l = mid + 1; // 如果条件满足，增加下界 l
} else {
r = mid - 1; // 如果不满足条件，减小上界 r
}
}
// 输出结果，l - 1 是最大的满足条件的 mid
System.out.println(l - 1);
sc.close(); // 关闭 Scanner
}
}
-
读取输入:
int n = sc.nextInt();和int m = sc.nextInt();：分别读取整数n和m，表示数组的大小和查询的数量。long[] a = new long[n + 1];：创建一个大小为n+1的数组a，索引从 1 开始存储。for (int i = 1; i <= n; i++) a[i] = sc.nextLong();：从控制台读取数组a的值。
-
读取查询区间:
List<int[]> arr = new ArrayList<>();：创建一个列表arr用于存储查询的左右区间[l, r]。for (int i = 0; i < m; i++) { ... }：循环读取m个查询的左右边界l和r，并将它们以数组的形式存入arr列表。
-
初始化二分查找的上下界:
int l = 1; int r = m;：初始化左右边界l和r用于二分查找。
-
二分查找:
while (l <= r) { ... }：进入二分查找循环，循环条件是l <= r。int mid = (l + r) / 2;：计算当前二分查找的中间值mid。int[] A = new int[n + 2];：创建一个差分数组A，用于计算前缀和。
-
差分数组的应用:
for (int i = 0; i < mid; i++) { ... }：遍历前mid个查询，使用差分方法对数组A进行标记。A[aStart] += 1; A[aEnd + 1] -= 1;：标记差分数组的起始和结束位置。
-
前缀和计算与条件检查:
for (int i = 1; i <= n && ok; i++) { ... }：遍历数组A，计算前缀和并检查是否超过数组a中的值。if (A[i] > a[i]) ok = false;：如果差分数组的值大于原数组a中对应位置的值，则不满足条件。
-
更新二分查找的上下界:
if (ok) l = mid + 1;：如果当前中间值mid对应的查询符合条件，则增加下界。else r = mid - 1;：否则减小上界。
-
输出结果:
System.out.println(l - 1);：最后输出l - 1，即最大能满足条件的查询个数。
