一道C语言题 求 一个数组中 连续数字的最大和

Question

题目要求是 在一个文件p33data 中 有N个数字
这个文件从argv[1] 中被读取 N被argv[2]读取
需要输出这一个数组中 连续数字的最大和
列如 -3 100 -4 -2 9 -63 -200 55 输出就是103（就是连续数字 100 -4 -2 9 的和）

如果最大和为负数 则输出 0 最大和可以是整个数组的和
列如 1 4 3 -4 8 输出就是 12

Answer 1

题目描述：有31，-41，59，26，-53，58，97，-93，-23，84十个数。SUM（N，M）表示从第N个数到到第M个数的和。例如：SUM（2，3）=-41+59=18。问：最大的和是多少？对应的N和M是多少?

算法思想：数组中的数字可以看做用负数分割开的一段一段正数，先找出这几段正数中和最大的那段（这题的结果的那串数字必定包括和最大的那串正数）然后慢慢的向两边扩散。文字功底不是很好
不太会描述 大家看程序注释吧

#include <stdio.h>
#define MAXN10
int main(void)
{
int a[10] = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84};
int positive[MAXN];
int i, j, k;
int flag;
int max, temp;
int left, right;
i = j = 0;
while (a[i] < 0)//该循环从左侧开始找第一个非负数 i记录其下标
++i;
max = 0;
temp = 0;
//该循环找到整个数组中和最大的连续正数
//并用left和right分别记录该段连续正数最左边和最右边两个正数的下标
for (k=0; i<10; ++i) {
if (a[i] >= 0) {
j = i;
while (a[i] >= 0 && i < 10)
temp += a[i++];
if (temp > max) {
left = j;
right = i-1;
max = temp;
}
positive[k++] = temp;
temp = 0;
}
}
flag = 0;
temp = 0;
for (i=left-1; i>=0; --i) {
if (a[i]<0 && !flag) { //向左边扩散 先把连续的n个负数加起来
temp += a[i];
} else {//碰到了第一个正数
flag = 1;
if (a[i]>=0 && flag) {//把碰到的连续几个正数加起来
temp += a[i];
} else if (a[i]<0 && flag) {//又碰到了一个负数
if (temp >= 0) {//收益为正数 可以加上
left = i+1;
max += temp;
temp = 0;
++i;
flag = 0;
continue;
} else {//收益为负数 结束循环
break;
}
}
}
}
//printf("%d %d %d\n", left, right, max);
flag = 0;
temp = 0;
for (j=right+1; j<10; ++j) {
if (a[j]<0 && !flag) {
temp += a[j];
} else {
flag = 1;
if (a[j]>=0 && flag) {
temp += a[j];
} else if (a[j]<0 && flag) {
if (temp >= 0) {
right = j-1;
max += temp;
temp = 0;
--j;
flag = 0;
continue;
} else {
break;
}
}
}
}
printf("N = %d M = %d SUM = %d\n", left, right, max);
return 0;
}

Answer 2

这么简单的题，网上搜索以下一堆讲解。