剑指Offer - 九度1372 - 最大子向量和（连续子数组的最大和）
2013-11-23 16:25
- 题目描述：
-
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天JOBDU测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？
- 输入：
-
输入有多组数据,每组测试数据包括两行。
第一行为一个整数n(0<=n<=100000),当n=0时,输入结束。接下去的一行包含n个整数(我们保证所有整数属于[-1000,1000])。
- 输出：
-
对应每个测试案例,需要输出3个整数单独一行,分别表示连续子向量的最大和、该子向量的第一个元素的下标和最后一个元素的下标。若是存在多个子向量,则输出起始元素下标最小的那个。
- 样例输入：
-
3
-1 -3 -2
5
-8 3 2 0 5
8
6 -3 -2 7 -15 1 2 2
0
- 样例输出：
-
-1 0 0
10 1 4
8 0 3
题意分析：
经典的问题，找出最大子数组的和。首先扫描一遍，看有没有正数。如果所有元素都是非正数，那么取最大的元素作为结果即可。否则要再O(n)扫一遍。
定义sum为当前字段和，msum为sum的最大值。
从a[0]开始扫描，定义sum为当前的子段和，如果sum > msum则更新msum，如果sum < 0则表示这段和已经小于0，因此不可能从这段得到最大值，这时从下一个元素开始扫描，并将sum重置为0。所有元素遍历完了，msum即为结果。
时间复杂度O(n)，空间复杂度O(1)。
// 653468 zhuli19901106 1372 Accepted 点击此处查看所有case的执行结果 1416KB 1021B 430MS
//
#include <climits>
#include <cstdio>
using namespace std; int main()
{
int *a = NULL;
int n, i;
int max_v;
int ll, rr;
int ml, mr;
int sum, msum; while(scanf("%d", &n) == && n > ){
a = new int[n];
if(a == NULL){
return ;
} max_v = INT_MIN;
ml = mr = ;
for(i = ; i < n; ++i){
scanf("%d", &a[i]);
if(a[i] > max_v){
max_v = a[i];
ml = i;
mr = i;
}
}
if(max_v <= ){
// no positive number in the array
printf("%d %d %d\n", max_v, ml, mr);
}else{
sum = ;
msum = ;
ll = ;
for(i = ; i < n; ++i){
sum += a[i];
if(sum < ){
ll = i + ;
sum = ;
}else{
rr = i;
}
if(sum > msum){
msum = sum;
ml = ll;
mr = rr;
}
} printf("%d %d %d\n", msum, ml, mr);
} delete a;
a = NULL;
} return ;
}