算法4：求整型数组的连续子数组的最大和

2019-11-06 06:51:07

字体：大中小

来源：转载

供稿：网友

算法4：求整型数组的连续子数组的最大和

输入一个整型数组，数组里既有正数也有负数，数组中连续一个或者多个组成整型子数组，每个子数组都有一个和，求所有子数组的最大和，要求时间复杂度为O(n)。

解题思路

使用贪婪算法，数组从开始往后遍历，记录最大和，当前和小于0时，当前子数组和置为0.

c++代码如下

//使用贪婪算法，遇到sum<0的情况，就将sum置0void GetSubMaxSum(int srcBuffer[],int srcBufferLen,int maxSubBuffer[],int& maxSubLength,int& maxSum){ if(srcBuffer == NULL || srcBufferLen <= 0) { maxSubBuffer = NULL; maxSum = 0; return; } maxSum = 0; int maxSubBufferLen = 0; int sum = 0; int beginIndex = 0; int endIndex = 0; for(int i = 0; i < srcBufferLen; i++) { sum +=srcBuffer[i]; if(sum > maxSum) { endIndex = i; maxSum = sum; } if(sum <= 0) { beginIndex = i; sum=0; } } maxSubLength = 0; for(int i = beginIndex; i <=endIndex; i++) { maxSubBuffer[maxSubLength++]=srcBuffer[i]; }}

测试代码如下

int _tmain(int argc, _TCHAR* argv[]){ const int srcLength = 10; int srcBuffer[srcLength] = {0}; cout<<"please input 10 int valude"<<endl; for(int i = 0; i < srcLength;i++) { cin>>srcBuffer[i]; } int maxSubBuffer[srcLength] = {0}; int maxSum = 0; int maxSubLength = 0; GetSubMaxSum(srcBuffer,srcLength,maxSubBuffer,maxSubLength,maxSum); cout<<"maxsum = "<<maxSum<<endl; for(int i = 0; i < maxSubLength; i++) { cout<<maxSubBuffer[i]<<" "; } cout<<endl; return 0;}

上一篇：Eclipse快捷键大全

下一篇：[Leetcode] 27. Remove Element

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注