首页 > 代码库 > 编程之美之子数组之和的最大值以及扩展(可首尾相连)
编程之美之子数组之和的最大值以及扩展(可首尾相连)
情形一:不允许首尾相连
此情况很常见,方法是动态规划,编程之美的方法三给出了解法,这里就直接给出代码了
int maxSubSum(vector<int>& data) { int length = data.size(); assert(length >= 0); int maxSum = data[length-1],startSum = data[length-1],begin = length-1,i; for(i = length-2;i >= 0;i--) { startSum = max(data[i],data[i]+startSum);//以第i个数开头的最大子数组之和 if(startSum > maxSum) { begin = i; maxSum = startSum;//当前的最大子数组之和 } } startSum = 0; for(;begin < length && startSum != maxSum;startSum+=data[begin],begin++)cout << data[begin] << " "; cout << endl; return maxSum; }情形二、数组可以首尾相连
问题的解可以分为两种情况:
1)解没有跨过A[n-1]到A[0],即普通的求子数组和的最大值2)解跨过A[n-1]到A[0]
对于第2种情况包含两种可能(2.1)包含整个数组;(2.2)包含两个部分,从A[0]开始的一段以及以A[n-1]结尾的一段,这种情况相当于从数组A中删除一个和最小的一个子数组,而当最小和为0时,即全为非0元素时,此时又和(2.1)一样。而个人认为解跨过A[n-1]到A[0]的情况肯定大于没有跨过的情况,所以,最后的结果就是所有元素的和减去绝对值最大的负数子数组,具体代码如下:
int maxSubSumEndToEnd(vector<int>& data) { int length = data.size(); assert(length >= 0); int minSum = data[length-1],startSum = data[length-1],allSum = data[length-1],begin = length-1,i,j; for(i = length-2;i >= 0;i--) { allSum += data[i]; startSum = min(data[i],data[i]+startSum); if(startSum < minSum) { begin = i; minSum = startSum;//求绝对值最大的负数子数组 } } if(minSum > 0) { minSum = 0; begin = 0; } startSum = 0; j = begin; for(;j < length && startSum != minSum;startSum+=data[j],j = (j + 1)%length);//找到开始的位置j for(i = j;i != begin;i = (i+1)%length)cout << data[i] << " "; cout << endl; return (allSum - minSum); }如有问题,请指正,谢谢
编程之美之子数组之和的最大值以及扩展(可首尾相连)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。