作者主页：Designer 小郑 作者简介：Java全栈软件工程师一枚，来自浙江宁波，负责开发管理公司OA项目，专注软件前后端开发（Vue、SpringBoot和微信小程序）、系统定制、远程技术指导。CSDN学院、蓝桥云课认证讲师，全栈领域优质创作者，在校期间参加PAT乙级考试获得满分，三年ACM竞赛经验，斩获国奖两项，省奖五项。热爱技术、专注业务、开放合作、乐于分享，期待你我共同成长！ 主打方向：Vue、SpringBoot、微信小程序
题目链接：题目链接
题面：
小王再次体验太空弹簧后，还是觉得飞机好玩，于是又来到了太空飞机场，想开着飞机遨游太空。
小张看到小王对太空飞机场如此感兴趣，于是命令手下将飞机场调整成了环形的一个有序圈，圈的周长为 N（1 < N < 5000)，也就是说一圈有 N 个飞机位，让小王玩得痛快。
这些临时排列的飞机场，每个飞机位都放有一张卡牌，卡牌上有个数 M（-5000 < N < 5000)，飞机飞到这个飞机位后，必须翻开这张卡牌，自己的积分加上这个数。
小王的飞机可以从九点钟开始，任意选一个飞机场作为启点，顺时针方向驾驶飞机，必须逐个停留每个飞机位，不得跨越，终点设为九点钟方向往南的第一个飞机位，飞机位编号如图所示。
游戏开始之前小王已经知道了每个飞机位的卡牌值，请问小王如何飞行才能让自己的积分最大化？
引用说明：以上图片来自于蓝桥云课。
知识点
- 最大子数组和
- 动态规划
初始代码
代码语言：javascript复制public class HMain {
public static List<Integer> doWork(List<Integer> inputList) {
List<Integer> ansObj = new ArrayList<>();
// 最大积分值
int max = -999;
// 起始飞机位
int k = 0;
// 终止飞机位
int l = 0;
//代码编辑区 开始
//代码编辑区 结束
ansObj.add(max);
ansObj.add(k);
ansObj.add(l);
return ansObj;
}
public static void main(String[] args) {
//测试用例
System.out.println((Objects.equals(Arrays.asList(8,3,6),doWork(Arrays.asList(1,-2,3,4,-5,6,-7))) ? "【√正确】" : "【X错误】 ") "圈卡片值：1,-2,3,4,-5,6,-7，答案：" doWork(Arrays.asList(1,-2,3,4,-5,6,-7)));
System.out.println((Objects.equals(Arrays.asList(21,5,7),doWork(Arrays.asList(5,6,8,-99,7,7,7))) ? "【√正确】" : "【X错误】 ") "圈卡片值：5,6,-1,5,4,-7，答案：" doWork(Arrays.asList(5,6,8,-99,7,7,7)));
}
}样例说明
输入数据是一个整数数组 A，代表飞机场从九点钟方向开始，顺时针逐个飞机位的卡片值，数组长度不超过 5000，数组数据项的绝对值不超过 5000。
题目需要返回三个数 max（小王最高可获得的积分）、k（起始位置）、l（终止位置）。
题解
考察对动态规划的理解。九点钟方向顺时针一圈，可以理解为一条直线，卡片值也就是一个一维数组。
状态转移方程为 dp[i] = dp[i] dp[i-1]，若 dp[i-1] 大于 0 则说明前面的积分可以延续采用。
若小于 0 则放弃前面的积分，从 0 积分重新开始，并更新起始位置。
参考代码如下：
代码语言：javascript复制import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;
public class HAns {
private final static Integer[] ans = new Integer[6000];
public static List<Integer> doWork(List<Integer> inputList) {
List<Integer> ansObj = new ArrayList<>();
// 最大积分值
int max = -999;
// 起始飞机位
int k = 0;
// 终止飞机位
int l = 0;
//代码编辑区 开始
int n = inputList.size();
List<Integer> numberList = new ArrayList<>();
numberList.add(0);
numberList.addAll(inputList);
for(int i = 0; i < 6000; i ) {
ans[i] = 0;
}
for(int i = 1; i <= n; i ) {
ans[i] = Math.max(numberList.get(i), ans[i - 1] numberList.get(i));
if (ans[i] > max) {
max = ans[i];
l = i;
}
}
int sum = 0;
for (int i = l; i > 0; i--) {
sum = numberList.get(i);
if (sum == max) {
k = i;
}
}
//代码编辑区 结束
ansObj.add(max);
ansObj.add(k);
ansObj.add(l);
return ansObj;
}
public static void main(String[] args) {
//测试用例
System.out.println((Objects.equals(Arrays.asList(8,3,6),doWork(Arrays.asList(1,-2,3,4,-5,6,-7))) ? "【√正确】" : "【X错误】 ") "圈卡片值：1,-2,3,4,-5,6,-7，答案：" doWork(Arrays.asList(1,-2,3,4,-5,6,-7)));
System.out.println((Objects.equals(Arrays.asList(21,5,7),doWork(Arrays.asList(5,6,8,-99,7,7,7))) ? "【√正确】" : "【X错误】 ") "圈卡片值：5,6,8,-99,7,7,7，答案：" doWork(Arrays.asList(5,6,8,-99,7,7,7)));
}
}总结
要 AC 本题，必须学会最大子数组和和动态规划的算法，尽可能的获取卡片，以获取最高的积分，最终通过本题。
