#yyds干货盘点# 动态规划专题：不相邻取数

paranoid lv.1

发布时间：2022-11-05 02:48:07 346

相关标签： # java# java

1.简述：

描述

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

输入描述：

第一行输入一个正整数，代表数组长度

第二行输入个正整数，代表整个数组。

输出描述：

不相邻的数的最大和。

示例1

输入：

4
2 6 4 1

输出：

说明：

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

文章来源： https://blog.51cto.com/u_15488507/5817861

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。