题目链接：题目链接
题面：
小王再次体验太空弹簧后，还是觉得飞机好玩，于是又来到了太空飞机场，想开着飞机遨游太空。
小张看到小王对太空飞机场如此感兴趣，于是命令手下将飞机场调整成了环形的一个有序圈，圈的周长为 N（1 < N < 5000)，也就是说一圈有 N 个飞机位，让小王玩得痛快。
这些临时排列的飞机场，每个飞机位都放有一张卡牌，卡牌上有个数 M（-5000 < N < 5000)，飞机飞到这个飞机位后，必须翻开这张卡牌，自己的积分加上这个数。
小王的飞机可以从九点钟开始，任意选一个飞机场作为启点，顺时针方向驾驶飞机，必须逐个停留每个飞机位，不得跨越，终点设为九点钟方向往南的第一个飞机位，飞机位编号如图所示。
游戏开始之前小王已经知道了每个飞机位的卡牌值，请问小王如何飞行才能让自己的积分最大化？
引用说明：以上图片来自于蓝桥云课。
知识点
- 最大子数组和
- 动态规划
初始代码
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 积分重新开始，并更新起始位置。
参考代码如下：
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 本题，必须学会最大子数组和和动态规划的算法，尽可能的获取卡片，以获取最高的积分，最终通过本题。
