华为OD 跳格子2（200分）【java】B卷

华为OD统一考试A卷+B卷 新题库说明
你收到的链接上面会标注A卷还是B卷。目前大部分收到的都是B卷。
B卷对应20022部分考题以及新出的题目，A卷对应的是新出的题目。
我将持续更新最新题目
我精选了一部分题目免费分享给大家，可前往夸克网盘转存，请点击以下链接进入：

我用夸克网盘分享了「华为OD题库Java.zip」，点击链接即可转存。
链接：https://pan.quark.cn/s/f1a7e6aec5ac

题目描述：

小明和朋友玩跳格子游戏， 有 n个连续格子组成的圆圈，每个格子有不同的分数，小朋友可以选择从任意格子起跳，但是不能跳连续的格子，不能回头跳，也不能超过一圈 ;
给定一个代表每个格子得分的非负整数数组，计算能够得到的最高分数。

输入描述：
给定一个数例，第一个格子和最后一个格子收尾相连，如：2 3 2

输出描述：
输出能够得到的最高分，如：3

补充说明： 1 <= nums.length <= 100 0 <= nums[i] <= 1000

示例1
输入： 2 3 2
输出： 3
说明： 只能跳3这个格子，因为第一个格子和第三个格子收尾相连

示例2
输入： 1 2 3 1
输出： 4
说明： 1+3=4

解题思路：
使用动态规划思想

参考代码

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] a = new int[100];
        int n = 0;
        while(sc.hasNextInt()) {
            a[n++] = sc.nextInt();
        }
        int[] dp = new int[n];
        int ans = 0;
        for(int i = 0; i < n- 1; i++) {
            if(i >= 2) {
                dp[i] = Math.max(dp[i- 1], dp[i - 2] + a[i]);
            } else {
                dp[i] = a[i];
                if(i > 0) dp[i] = Math.max(dp[i], dp[i-1]);
            }
            if(dp[i] > ans) {
                ans = dp[i];
            }
        }
        int[] f = new int[n];
        for(int i = 1; i < n; i++) {
            if(i >= 2) {
                f[i] = Math.max(f[i- 1], f[i - 2] + a[i]);
            } else {
                f[i] = a[i];
                if(i > 0) f[i] = Math.max(f[i], f[i-1]);
            }
            if(f[i] > ans) {
                ans = f[i];
            }
        }
        System.out.println(ans);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38