描述

小红拿到了一个数组。她想取一些不相邻的数，使得取出来的数之和尽可能大。你能帮帮她吗？

思路

这道题是让求数组不相邻的最大和，大家想一想，对于第一个元素肯定本身就是最大和了；第二个元素的最大和是 第一个元素和第二个元素中最大的那个；第三个元素的最大和则是 （第三个元素 + 第一个元素） 和 第二个元素 最大值；第四个元素最大和则是 第四个元素 + 第二个元素所在位置的最大和） 和 第三个元素所在位置的最大和 最大值；

说到这里是不是就能看出来点东西，从第三个元素开始，每个位置最大和是：Math.max(当前元素 + 前第二个元素所在位置最大和， 前第一个元素所在位置最大和)，第一个和第二个元素最大和的求法也在上面说过了，这个公式则是 动态规划的【状态转移方程】。

AC 代码

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];
    }
}

• 时间复杂度：O(N)， N 为数组长度，需要每个元素遍历一遍
• 空间复杂度：O(N)， N 为数组长度，创建 dp 数组