- 前言
- 分析
- ① 数列的正整数不多于一个
- ② 数列的正整数多于一个
- ③ 最大子数列和的最小子数列
时间：2021年11月8日
作者：返祖猿
参考：7-1 最大子列和问题 (20 分)
题目集：数据结构与算法题目集（中文）
题目：7-1 最大子列和问题 (20 分)
题目大意：给一个带有正、负整数的数列，求子数列最大的和。
不会做所以百度，看到参考文章后有一些想法，记录在此。
分析 ① 数列的正整数不多于一个题目中说了如果数列中全是负数，则输出零，就令人忍不住思考它本来应该输出什么，答案倒是很容易想到：输出最大的负数。
那么扩展一下，当一个数列的正整数不多于一个时，数列的最大子数列和就是这个数列中最大的数。
具体做法是：
在输入时统计正整数个数，同时记录最大的数。
int countPositive = 0, max, index;
scanf("%d", &a[0]);
max = a[0];
index = 0;
if(a[0]>0){
countPositive ++;
}
for(i=1; i0){
countPositive ++;
}
if(max
② 数列的正整数多于一个
这里就是稍微有点难度的部分了，首先要理解一下两点：
- 子数列是数列中连续的一串，而不能是断续的。
- 由于前提条件，最大子数列和必然是个正数。
最大子数列和必然是个正数，那么对于数列中的某个正数来说，如果这个正数前面的子数列和小于或等于 0，那么最终子数列不必甚至不能包含这串子数列，除非最终子数列就在这串子数列中。
从第一个正数开始，如果它与下一个元素的和大于零，那么继续向下统计；如果它与下一个元素的和小于零，那么子数列和的极大值将在它与第三个元素之间产生；如果第三个元素是正数，且与第四个元素的和依然是正数，那么子数列和的极大值将在它与从第三个元素开始的子数列之间产生。
来看算法：
sum = 0;
max = 0;
for(i=0;imax)
max=sum;
else if(sum<0)
sum=0;
}
-
最初，sum 持续更新 max，直到 sum 达到第一个极大值；
-
如果 sum 变小了，但是没变得比 0 更小，后续又变得比 max 更大，那么 sum 将继续更新 max；
-
直到 sum<0，此时出现一个节点，这个节点之前的子数列要么已经包含了最终子数列，要么与最终子数列没有任何关系，因为 sum<0，如果依旧用 sum 来对后续子数列求和，所得结果不会比从零开始对后续子数列求和得到的结果大；
-
sum 置 0，然后重新统计后续的子数列和，新的 sum 与 max 比较，如果 sum>max，说明最终子数列是后面的子数列，否则子数列仍然包含在前面的子数列中；
-
无论如何，返回第二步，直至到达最后一个元素。
至此，最大子数列和有了结果。
记录子数列开始与结束的版本：
sum = 0; max = 0;
int indexS = 0, indexE = 0, indexT = 0;
int flag = 0;
for(i=0; i0 && flag == 0){
flag = 1;
indexT = i;
}
if(sum>max){
max = sum;
indexS = indexT;
indexE = i;
} else if(sum<0){
sum = 0;
flag = 0;
}
}
----------------------------------------------------------------
最大子数列和：max
最大子数列：{a[indexS], ..., a[indexE]}
③ 最大子数列和的最小子数列
以上算法在计算下方数据时：
4
1 -1 1 1
得到的子数列是：
{1, -1, 1, 1}
可以看到前面两个元素的和为零，可以去掉。
只需要将 sum 置零的条件 sum<0 改为 sum<=0 就可以了。
