2023华为OD机试真题-跳格子2JAVA、Python、C++)_跳格子2算法

题目描述：

小明和朋友玩跳格子游戏， 有 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);
    }
}