首页 > 代码库 > 编程之美——子数组和最大值
编程之美——子数组和最大值
解法一：直接求解下标i~j的子数组和最大值；复杂度O(N^2)；
代码如下：
1 #include<iostream> 2 using namespace std; 3 const int INF=1000000; 4 5 int maxSum(int arr[],int n); 6 7 int main() 8 { 9 int arr[7]={-2,5,3,-6,4,-8,6};10 cout<<maxSum(arr,7)<<endl;11 return 0;12 }13 14 int maxSum(int arr[],int n)15 {16 int result=-INF;17 int sum;18 for(int i=0;i<n;++i)19 {20 sum=0;21 for(int j=i;j<n;++j)22 {23 sum+=arr[j];24 if(sum>result)25 result=sum;26 }27 }28 return result;29 }
解法二：使用分治法求解
原数组最大子数组可能位于mid左边，mid右边，或者横跨mid，求出其最大值即可；
算法复杂度O(NlogN);
代码如下：
1 #include<iostream> 2 using namespace std; 3 4 const int INF=1000000; 5 6 int maxSum(int arr[],int l,int h); 7 int findMid(int arr[],int low,int mid,int high); 8 int maxNum(int a,int b,int c); 9 10 int main()11 {12 int arr[7]={100,101,-300,1,2,3,4};13 cout<<maxSum(arr,0,6)<<endl;14 return 0;15 }16 17 int maxSum(int arr[],int low,int high)18 {19 int sum1,sum2,sum3;20 21 //只有一个元素22 if(low==high)23 return arr[low];24 else25 {26 int mid=(low+high)/2;27 sum1=maxSum(arr,low,mid);28 sum2=maxSum(arr,mid+1,high);29 sum3=findMid(arr,low,mid,high);30 31 return maxNum(sum1,sum2,sum3);32 }33 }34 35 //计算的最大子数组和横跨左右两个数组，求其最大值36 int findMid(int arr[],int low,int mid,int high)37 {38 int sumLeft=-INF;39 int sumRight=-INF;40 41 int sum=0;42 //向左43 for(int i=mid;i>=low;--i)44 {45 sum+=arr[i];46 if(sum>sumLeft)47 sumLeft=sum;48 }49 50 sum=0;51 for(int i=mid+1;i<=high;++i)52 {53 sum+=arr[i];54 if(sum>sumRight)55 sumRight=sum;56 }57 return (sumLeft+sumRight);58 }59 60 int maxNum(int a,int b,int c)61 {62 int num=max(a,b);63 return max(num,c);64 }
解法三：对数组进行一次遍历，时间复杂度O(N)；
1 #include<iostream> 2 using namespace std; 3 4 int maxSum(int arr[],int n); 5 6 int main() 7 { 8 int arr[7]={-2,5,3,-6,4,-8,6}; 9 cout<<maxSum(arr,7);10 return 0;11 }12 13 int maxSum(int arr[],int n)14 {15 int max=arr[0];16 int sum=0;17 18 for(int i=0;i<n;++i)19 { 20 //若之前子数组和小于0，舍去，否则累加21 if(sum<0)22 sum=arr[i];23 else24 sum+=arr[i];25 if(sum>max)26 max=sum;27 }28 return max;29 }
若问题推广：求二维数组中被矩形框起来数字和的最大值，该怎么解决呢？
思路：对N*M矩阵，先确定上下边界，之后将每一列数据相加—》一维情况，复杂度O(N^2*M);
若二维数组首尾相连成圆筒状，而采取分治法，同一维，分三种情况。
若二维数组上下相连成游泳圈状，问题有待解决；
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。