#yyds幹貨盤點# 動态規劃專題：不相鄰取數

1.簡述：

描述

小紅拿到了一個數組。她想取一些不相鄰的數，使得取出來的數之和盡可能大。你能幫幫她嗎？

輸入描述：

第一行輸入一個正整數  ，代表數組長度

第二行輸入  個正整數  ，代表整個數組。

輸出描述：

不相鄰的數的最大和。

示例1

輸入：

4
2 6 4 1      

輸出：

7      

取 6 和 1 即可      

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