1.简述：
小红拿到了一个数组。她想取一些不相邻的数，使得取出来的数之和尽可能大。你能帮帮她吗？
第一行输入一个正整数 
，代表数组长度
第二行输入 
个正整数 
，代表整个数组。
不相邻的数的最大和。
输入：
4
2 6 4 1
输出：
7
说明：
取 6 和 1 即可
2.代码实现：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 输入长度
long n = Long.parseLong(sc.nextLine());
// 输入数组
String[] arrStr = sc.nextLine().split(" ");
long[] arr = new long[arrStr.length];
for (int i = 0; i < arrStr.length; i++) {
arr[i] = Long.parseLong(arrStr[i]);
}
long run = run(arr.length, arr);
System.out.println(run);
}
public static long run(int n, long[] arr) {
if (arr == null || arr.length < 1) {
return -1;
}
if (arr.length == 1) {
return arr[0];
}
if (arr.length == 2) {
return Math.max(arr[0], arr[1]);
}
// 创建 dp 数组
long[] dp = new long[n];
dp[0] = arr[0];
dp[1] = Math.max(arr[0], arr[1]);
// 状态转移
for (int i = 2; i < arr.length; i++) {
long a = dp[i - 2] + arr[i];
long b = dp[i - 1];
dp[i] = Math.max(a, b);
}
return dp[n - 1];
}
}
