赞
踩
最大连续子数组:给定一组有正有负的数组,从中找出和最大的连续子数组。
一 暴力求解
设置两个for循环,分别求从1\2\3……个元素为起始元素的最大子数组和。过程中不断使用if条件判断更新maxsum的值。时间复杂度O(n2)。
代码如下:
- #include <bits/stdc++.h> //万能头文件
- using namespace std;
- int main()
- {
- int n;//数组长度
- while(cin>>n)
- {
- int a[n+5];
- for(int i=0;i<n;i++)
- {
- cin>>a[i];
- }
- int MaxSum,ThisSum;
- MaxSum=0;
- for(int i=0;i<n;i++)
- {
- ThisSum=0;
- for(int j=i;j<n;j++)
- {
- ThisSum+=a[j];
- if(ThisSum>MaxSum) MaxSum=ThisSum;
- }
- }
- cout<<MaxSum<<endl;
- }
- }
二 分治求解
步骤:
1. 将序列分为左右两个子数组
2. 递归地求两个子数组的最大和和
3. 从中间的点分别找出左右,跨过分界线的最大子数组的和
4.
代码如下:
- #include <iostream>
- using namespace std;
- int MAX3(int A,int B,int C)
- {
- return A>B?A>C?A:C:B>C?B:C;
- }
- int DivideandConquer(int a[],int left,int right)
- {
- int MaxleftSum,MaxrightSum;//左右两子数组中的最大子数组和
- int MaxleftborderSum,MaxrightborderSum;//经过中点的左右子数组最大和
- int LeftborderSum,RightborderSum;//过程量
- int center,i;
- if(left == right) //递归终止条件,子数组只有一个数字
- return a[left];
- center=(left+right)/2;
- MaxleftSum=DivideandConquer(a,left,center);
- MaxrightSum=DivideandConquer(a,center+1,right);
- //跨界求最大子数组和
- MaxleftborderSum = 0; LeftborderSum = 0;
- for (i = center; i >= left; i--)
- {
- LeftborderSum += a[i];
- if(LeftborderSum > MaxleftborderSum)
- MaxleftborderSum = LeftborderSum;
- }//左边扫描结束
- MaxrightborderSum = 0; RightborderSum = 0;
- for (i = center+1; i < right; i++)
- {
- RightborderSum += a[i];
- if(RightborderSum > MaxrightborderSum)
- MaxrightborderSum = RightborderSum;
- }//右边扫描结束
- return MAX3(MaxleftSum,MaxrightSum,MaxleftborderSum+MaxrightborderSum);
- }
- int MaxSubseq3(int a[],int n)
- {
- return DivideandConquer(a,0,n-1);
- }
- int main()
- {
- int n;
- while(cin>>n)
- {
- int a[n+5];
- for(int i=0;i<n;i++)
- {
- cin>>a[i];
- }
- cout<<MaxSubseq3(a,n);
- }
- }
使用一个for循环,只要sum的值小于0就丢弃,重新计数。
此法需保证数组元素有正有负。
因为有正有负,所以最大值一定大于0。
- int Maxsubseqdp(int a[],int n)
- {
- int ThisSum,MaxSum;
- MaxSum=0;
- ThisSum=0;
- for(int i=0;i<n;i++)
- {
- ThisSum+=a[i];
- if(ThisSum>MaxSum) MaxSum=ThisSum;
- else if(ThisSum<0) ThisSum=0;
- }
- return MaxSum;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。