赞
踩
问题描述
给定(可能是负的)整数序列A1, A2,...,AN, 寻找(并标识)使Sum(Ak)(k >=i, k <= j)的值最大的序列。如果所有的整数都是负的,那么连续子序列的最大和是那个最大的负数项。最好给出给出最大和连续子序列!!
1 暴力破解法
这个问题有一个最简单直接的穷举解决法。我们看问题,既然要求里面最大的连续子序列。那么所有的连续子序列将由哪些组成呢?以数组的第一个元素为例,连续子序列必须是至少包含元素A1,也可能包含从A1到A2...以及从A1到AN。这样就有N种可能。后面的元素也按照这样类似的办法,以该元素开始,包含该元素的单元素数组,两个元素数组...直到包含数组末尾的数组。
- #include <iostream>
- #include <cstdlib>
- #include <vector>
-
- using namespace std;
-
- int main()
- {
- vector<int> array;
- for(int i=0;i<20;i++)
- {
- int j = 50-random()%100; //-49~50
- array.push_back(j);
- }
-
- for(vector<int>::iterator it=array.begin();it!=array.end();++it)
- {
- cout<<*it<<" ";
- }
- cout<<endl;
- int maxsum=-50; //注意初始化
- int low=0;
- int high=0;
- for(int i=0;i<array.size();i++)
- {
- int sum=0;
-
- for(int j=i;j<array.size();j++)
- {
- sum+=array[j];
- if(sum>maxsum)
- {
- maxsum=sum;
- low=i;
- high=j;
- }
- }
- }
- cout<<"subarray:"<<array[low]<<"~"<<array[high]<<endl;
- cout<<"maxsun="<<maxsum<<endl;
- return 0;
- }
结果:
时间复杂度分析:两重循环遍历,复杂度为O(n^2)
2 分治策略(递归法)
对这个问题,有一个相对复杂的O(NlogN)的解法,就是使用递归。如果要是求出序列的位置的话,这将是最好的算法了(因为我们后面还会有个O(N)的算法,但是不能求出最大子序列的位置)。该方法我们采用“分治策略”(divide-and-conquer)。
在我们例子中,最大子序列可能在三个地方出现,或者在左半部,或者在右半部,或者跨越输入数据的中部而占据左右两部分。前两种情况递归求解,第三种情况的最大和可以通过求出前半部分最大和(包含前半部分最后一个元素)以及后半部分最大和(包含后半部分的第一个元素)相加而得到。
- #include <iostream>
- #include <cstdlib>
- #include <vector>
-
- using namespace std;
- /*
- * find a subarray crossing the mid with the biggist sum
- */
-
- int find_max_crossing_subarray(vector<int> array,int low, int mid, int high)
- {
- int left_maxsum=-50; //for sum
- int right_maxsum=-50; //for sum
- int sum =0;
- for(int i= mid;i>= low;--i)
- {
- sum += array[i];
- if(sum > left_maxsum)
- {
- left_maxsum=sum;
-
- }
- }
-
- sum=0;
- for(int i=mid+1;i<=high;++i)
- {
- sum += array[i];
- if(sum > right_maxsum)
- {
- right_maxsum=sum;
-
- }
- }
- return(left_maxsum+right_maxsum);
-
- //cout<<"maxsum_crossing_mid"<<left_maxsum+right_maxsum<<endl;
- }
-
- int max(int a, int b, int c)
- {
- if(a>=b && a>=c)
- return a ;
- else if(b>=a && b>=c)
- return b;
- else
- return c;
- }
- /*
- * find a subarray on the left or right side of mid
- */
- int find_max_subarray(vector<int> array, int low, int high)
- {
-
-
- if(low==high)
- {
-
- return array[low];
- }
- int mid = int((low+high)/2);
- int low_maxsum = find_max_subarray(array, low, mid);
- int high_maxsum = find_max_subarray(array, mid+1, high);
- int crossing_mid_maxsum = find_max_crossing_subarray(array, low, mid, high);
- return max(low_maxsum, high_maxsum, crossing_mid_maxsum);
- }
- int main()
- {
- vector<int> array;
- for(int i=0;i<10;i++)
- {
- int j = 50-rand()%100; //-49~50
- array.push_back(j);
- }
-
- for(vector<int>::iterator it=array.begin();it!=array.end();++it)
- {
- cout<<*it<<" ";
- }
- cout<<endl;
- int maxsum =find_max_subarray(array, 0, array.size()-1);
- cout<<"the maxsum="<<maxsum<<endl;
- //cout<<"range from"<<array[a[1]]<<"to"<<array[a[2]]<<endl;
- return 0;
- }
3 增量算法(插入算法)
假设已知A[1~N]的最大顺序子序列和,那么对于A[1~N+1]序列,增加一个项,最大顺序子序列和会在哪里产生呢?(1)不变,A[N+1]项不影响(2)在包括A[N+1]项往前的子序列中产生。
- #include <iostream>
- #include <cstdlib>
- #include <vector>
-
- using namespace std;
-
- int enlarge(vector<int> array,int maxsum, int i)
- {
- if(i>array.size() || i<=0)
- return -1;
- int sum=0;
- for(int j=i;j>=0;--j)
- sum += array[j];
- if(sum>maxsum)
- maxsum=sum;
- return maxsum;
- }
- int find_maxsum(vector<int> array)
- {
- if(array.empty())
- return -1;
- int maxsum=array.at(0);
- for(int i=1;i<=array.size()-1;++i)
- {
- int result = enlarge(array, maxsum, i);
- if(result>maxsum && result != -1)
- maxsum = result;
- }
- return maxsum;
- }
- int main()
- {
- vector<int> array;
- for(int i=0;i<10;++i)
- array.push_back(10-rand()%20);
- for(vector<int>::iterator it= array.begin();it != array.end();++it)
- cout<<*it<<" ";
- cout<<endl;
- int max = find_maxsum(array);
- cout<<"maxsum ="<<max<<endl;
- return 0;
- }
复杂度 O(n^2)
4 最优解(线性复杂度 O(N))
参考:http://www.cnblogs.com/CCBB/archive/2009/04/25/1443455.html
- //线性的算法O(N)
- long maxSubSum4(const vector<int>& a)
- {
- long maxSum = 0, thisSum = 0;
- for (int j = 0; j < a.size(); j++)
- {
- thisSum += a[j];
- if (thisSum > maxSum)
- maxSum = thisSum;
- else if (thisSum < 0)
- thisSum = 0;
- }
- return maxSum;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。