OD 算法题 B卷【跳格子2】

跳格子2

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

输入描述:
输入分数数组；第一个与最后一个首尾相连；
输出描述:
能够得到的最高分

示例1
输入：
2 3 2
输出：
3

示例2
输入：
1 2 3 1
输出：
4

示例3
输入：
3 5 7 1 2 4 1 9 10
输出：
23

python实现：

• 只有一个格子时，就跳这一个；
• 有两个格子时，跳一个最大分数的；
• 多个格子时，分情况0~n-2 or 1~n-1

def calc_score(start, end):pre, cur = 0, 0for i in range(start, end + 1):current = max(cur, pre + nums[i])  # cur 为当前最大值pre, cur = cur, currentreturn curdef skip(nums):if not nums:return 0n = len(nums)if n == 1:return nums[0]elif n == 2:return max(nums[0], nums[1])# 两种情况case1 = calc_score(0, n - 2)case2 = calc_score(1, n - 1)return max(case1, case2)# 读取输入
nums = list(map(int, input().split()))
# 输出结果
print(skip(nums))