9.17 中兴笔试面经 - 编程题 & 题解

考试时间：2023-09-17 (两小时)

考试题型： 单选10题（3分/题） + 多选5题（6分/题） + 编程2题（20分/题）

P1

​ 在荒野的大海上，有一群善良的海盗们，在他们的一次探险中，他们找到了一个神秘的环形岛屿，岛屿上隐藏着大量的宝藏，每个宝藏点都被标上了价值的数字，这些数字就是他们挖掘后可能获取的金币数量。然而，神秘的岛屿有一个诅咒，即任何相邻的两个宝藏点不能同时被挖掘，否则就会触发岛屿的防护机制，宝藏会消失。海盗们想要挖掘出尽可能多的宝藏，你能帮助他们找出应该挖掘哪些宝藏点吗?

输入描述

输入一系列数字，以空格隔开，表示环形岛屿上宝藏点的金币数量(因为是一个环形，所以第一个宝藏点和最后一个宝藏点是相邻的)。

输出描述

在满足规则，即不能连续挖掘两个相邻的宝藏点的基础上，算出挖掘的宝藏点的金币数量的最大值。

样例1

输入：
1 2 3

输出：
3

样例2

输入：
33 55 88 90 101

输出：
189

题解

动态规划

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

// P1
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        List<Integer> list = new ArrayList<>();
        while (in.hasNextInt()) {
            list.add(in.nextInt());
        }

        int max1 = solve(list.subList(0, list.size() - 1));
        int max2 = solve(list.subList(1, list.size()));
        System.out.println(Math.max(max1, max2));
    }

    public static int solve(List<Integer> list) {
        int n = list.size();
        int[][] dp = new int[n + 1][2];
        for (int i = 0;