连续子数组的最大和问题（五种解法） |
您所在的位置：网站首页 › 最大连续子序列和问题动态规划 › 连续子数组的最大和问题（五种解法） |
连续子数组的最大和问题（五种解法）
|
昨天（2021年5月29日）参加了软考软件设计师的考试，试卷上出现了一道算法题，问：连续子数组最大和的分治解法的时间复杂度，考完正好记录总结一下这道算法题。 求连续子数组的最大和题目描述： 输入一个整型数组，数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
比较常规的思路是暴力（O(n3)）、前缀和数组（O(n2)）两种，但是时间复杂度比较高，这题也可以用分治的策略做，时间复杂度O(nlogn)，还有两种时间复杂度为O(n)的做法，一种是动态规划，另一种是扫描法。这题需要掌握O(n)的解法。 解法 解法一：暴力法 O(n3) int MaxSumOfSub1(){ int res=-INF; for(int i=1;i int sum=0; for(int k=i;k if(l==r) return nums[l]; int mid=(l+r)/2; //计算Ma,Mb的情况 int maxa=MaxSumOfSub3(l,mid); int maxb=MaxSumOfSub3(mid+1,r); //计算子数组跨越两个子数组（Mc）的情况 int maxc,lmax=0,rmax=0,sum=0; for(int i=mid;i>=l;i--){//从中间元素开始往左累加的最大值 sum+=nums[i]; lmax=max(lmax,sum); } sum=0; for(int i=mid+1;i int res=-INF; int dp[N]; dp[0]=0; for(int i=1;i int res=-INF,sum=nums[0]; for(int i=2;i sum=nums[i]; }else{ sum+=nums[i]; } res=max(res,sum); } return res; } 运行结果 #include using namespace std; const int INF=0x3f3f3f3f,N=101000; int nums[]={0,31,-41,59,26,-53,58,97,-93,-23,84};//0不算,下标从1算 int cnt=10; int main(){ printf("暴力法：%d\n",MaxSumOfSub1()); printf("前缀和数组：%d\n",MaxSumOfSub2()); printf("动态规划：%d\n",MaxSumOfSub4()); printf("分治法：%d\n",MaxSumOfSub3(1,cnt)); printf("扫描法：%d\n",MaxSumOfSub5()); return 0; }
|
比如上面这个数组的子数组的最大和为187,从下标3到下标7的位置。（本文中数组下标从1开始）
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |