首页 > 代码库 > 求子数组的最大和
求子数组的最大和
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。
#include<stdio.h>int subStrSum(int* s, int len){ int i = 1, curSum = s[0], maxSum = s[0]; while(i < len) { if(curSum > 0 &&curSum + s[i] > 0)//当前和为负数或者加当前元素后为负数，则不进行累加，而赋当前和为当前元素 curSum += s[i]; else curSum = s[i]; i += 1; if(curSum > maxSum) maxSum = curSum; } return maxSum;}void main(){ int s[] = {-2,-2,-5,-2,-1,-6,-11,-7,-3}; int maxSum = subStrSum(s,9); printf("%d\n",maxSum);}
改进，输出该子数组
#include<stdio.h>typedef struct subStr{ int start; int length; int sum;}str;str subStrSum(int* s, int len){ str s1; int i = 1, curSum = s[0]; s1.start = 0; s1.length =1; s1.sum = s[0]; int length = 1, start = 0; while(i < len) { if(curSum > 0 &&curSum + s[i] > 0) { curSum += s[i]; length += 1; } else { curSum = s[i]; start = i; length = 1; } if(curSum > s1.sum) { s1.start = start; s1.length = length; s1.sum = curSum; } i += 1; } return s1;}void main(){ int s[] = {1,2,-5,2,1,6,-11,7,-3}; str str1 = subStrSum(s,9); int i ; for(i = 0; i < str1.length; i++) printf("%d,",s[str1.start+i]); printf("sum is %d\n",str1.sum);}
求子数组的最大和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。