给定一串数字求连续的最大和算法学习

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

算法思想：数组中的数字可以看做用负数分割开的一段一段正数，先找出这几段正数中和最大的那段（这题的结果的那串数字必定包括和最大的那串正数）然后慢慢的向两边扩散。文字功底不是很好不太会描述大家看程序注释吧(该算法有个缺陷就是当有几串连续正数的和相同时无法处理不过对于现在这个题目给定的数据中不存在这种情况但是如果让用户自己输入的话....所以大家有什么好的解决方法或者其他好的算法麻烦请给我留言)

#include #define MAXN 10int 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 = %dM = %dSUM = %d\n", left, right, max); return 0; }

【给定一串数字求连续的最大和】