首页 > 代码库 > 数组连续最大子和及环形数组最大子和
数组连续最大子和及环形数组最大子和
问题1：
/*求连续子数组的最大和：
* 设curSum为当前子数组(ai, ai+1, ......, aj)的和
* sum存放到目前为止子数组和的最大值
* 1. cursum+ai>0; cursum=cursum+ai
* 2. cursum+ai<=0; cursum=ai; */
1 int maxsubarr(vector<int> &a) 2 { 3 if(a.size()==0) 4 return 0; 5 int sum=0x80000000; //sum设为最小32位数 6 int cursum=0; 7 for(int i=0;i<a.size();i++) 8 { 9 if(cursum<=0)10 cursum=a[i];11 else12 cursum+=a[i];13 if(cursum>sum)14 sum=cursum;15 }16 return sum;17 }
由于cursum<0时，cursum取下个数组的值，当测试数据全为负数时，无法得到正确结果，比如：{-1，-5，-7，-3}；cursum会为-3,无法得到正确结果，有待解决。
问题2：
/*
求一维环形数组的连续子数组最大和--数组为a[n],a[n]环连接a[0]
问题分解为两种情况：
1. 最大和出现在 a[n-1]之前，即简化为非环形的连续子数组最大和，结果为max1
2. 最大和越过了a[n-1],a[0], 即成为环问题，由于一组数的和为定值，找出连续的最小和
* 用定值和减去连续的最小和，剩下的连续片段即为连续的最大和，结果为max2
* 求解连续的最小和时，可以利用问题1的函数求解最小和，（最小和肯定是负数导致）将数组所有元素取负，
* 那么求出的最大和即为最小和的负数形式。
* 最后比较max1和max2，取其中较大值。
*/
1 int maxcirclesub(vector<int> &a) 2 { 3 int max1,max2; 4 max1=maxsubarr(a); 5 int suma=0; 6 int len=a.size(); 7 vector<int> na(len); 8 for(int i=0;i<len;i++) 9 {10 suma+=a[i];11 na[i]=-a[i];12 } 13 max2=maxsubarr(na);14 max2=max2+suma;15 return (max1>max2)?max1:max2;16 }
其中maxsubarr为问题1中的函数。
数组连续最大子和及环形数组最大子和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。