前排广告位招租(●ˇ∀ˇ●) 前排给自己打广告！ 随缘更新的UP，翻唱/守望先锋/日常/……
我的Bilibili：非职业天使 欢迎关注、弹幕、评论、推荐、投币、收藏、转发分享~
题目：
给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为0，依此定义，所求的最优值为：
Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n
例如，当（a[1],a[2],a[3],a[4],a[5],a[6]）=(-2,11,-4,13,-5,-2)时，最大子段和为20。
-- 引用自《百度百科》
一、解题思路 Helden sterben nicht ！
1.解题技巧：
- 子段的前后两端一定不会是负数。由非负数开始，非负数结束，才能保证最大。
- 把全负数作为特殊情况，在最初输入时就判断出来，方便编程。
2.代码思路：
- 输入时判断数组内是否全部为负数。如果全负，直接输出0，结束程序。
- 当数组不是全负数时，调用求最大子段和函数MaxAn()求解，结束程序。
最大子段和函数MaxAn()中，利用for循环求前 i 项和，记为sum。最大子段和记为max，初值为a[0]。
在每次循环中max与sum对比。如果sum>max，那么max的值更新为sum。最后返回max值。
二、程序设计 Heros never die！
1.MaxAn()流程图
2.程序代码
1 public static int MaxAn(int a[]) {//求最大子段和
2 int max = 0;
3 int sum = a[0];
4 for(int i = 0;i < n;i++){
5 if(sum<0){ //子段首部舍去负数
6 sum = a[i];
7 }
8 else{
9 sum = sum + a[i]; //子段累计和
10 }
11 if(sum > max){
12 max = sum; //判断出最大和
13 }
14 }
15 return max;
16 }
1 public static void main(String[] args){
2
3 System.out.print("请输入数组内数字的个数：");
4 Scanner sc = new Scanner(System.in);
5 n = sc.nextInt();
6 System.out.print("请输入"+ n +"个数字:");
7 int[] a = new int[n];
8 for(int i = 0; i < n; i++)
9 {
10 a[i] = sc.nextInt();//控制台输入
11 if(a[i] >= 0){
12 flag = 1;//标记有正数（非全负数数组）
13 }
14 }
15 if(flag == 1){
16 System.out.print("最大子段和：" + MaxAn(a));
17 }
18 else{
19 System.out.print("最大子段和：0");
20 }
21 }
- 整体代码传送门→(๑•́ ₃ •̀๑)点我
- 初步运行如图所示。
三、自动测试 Till Valhalla！
1.测试用例设计
- 测试对象：计算最大子段和的函数MaxAn()。（由于程序是在main()中判断全负数数组的情况，条件过于简单，在此不进行具体测试设计。该情况在最初运行程序时已经通过测试，详见上图。）
- 覆盖标准：条件组合覆盖
- 流程图分析：从流程图我们可以得到四种组合覆盖情况：AC,AD,BC,BD（具体情况请将鼠标停留在流程图上查看，失效请点击图片）。由此设计以下数组，可以运行一次全部覆盖。
| 覆盖 | sum | max |
| AD | -1 | 0 |
| AC | 2 | 2 |
| BD | -1 | 2 |
| AC | 4 | 4 |
| BC | 9 | 9 |
2.自动测试
- 自动测试过程同上次作业。
- 测试结果如图所示。输入我们设计的数组得到了期待值9，测试通过，程序正确。
小记：
一直没敢写作业，以为会很难。没想到是个小程序，很轻易的写了出来。但是具体分析的话还是有很多说法的。比如老师给的博客就有五种解法，太厉害了。
最近把博客美化了。虽然没完工，但是让我有点喜欢写博客了。之前对博客一点好感都没有……而且美化有的地方被我弄坏了，有的东西都失效了……鼠标停留可以变图，还有博客下方的推荐按钮都被我弄坏了orz 绝望……