本文共 5088 字,大约阅读时间需要 16 分钟。
#include#include using namespace std;//s(tart)表示最大子序列的开始位置,e(nd)表示结束位置//这里如果有多于一个的最大子序列的时候,只记录开始位置最低的那个int s=0;int e=0;//穷举法,复杂度O(n^3)long maxSubSum1(const vector &a){ long maxSum=0; for (int i=0; i maxSum){ maxSum=thisSum; s=i; e=j; } } } return maxSum;}//也是穷举法,不过减去了上面的一些不必要操作O(n^2) long maxSubSum2(const vector &a){ long maxSum=0; for (int i=0; i maxSum){ maxSum=thisSum; s=i; e=j; } } } return maxSum;}long max3(long a, long b, long c){ if(a c) return a; else return c;}long maxSumRec(const vector a, int left, int right){ if(left == right) { //其实这个基准值在后面计算的时候可以保证 //在这里不必多此一举 if(a[left]>0) return a[left]; else return 0; } int center=(left+right)/2; long maxLeftSum=maxSumRec(a,left,center); long maxRightSum=maxSumRec(a,center+1,right); //某段序列中,求含最右侧元素序列和的最大值 long maxLeftBorderSum=0,leftBorderSum=0; for (int i=center; i>=left; i--) { leftBorderSum+=a[i]; if(leftBorderSum>maxLeftBorderSum) { maxLeftBorderSum=leftBorderSum; s=i; } } //某段序列中,求含最左侧元素序列和的最大值 long maxRightBorderSum=0,rightBorderSum=0; for (int j=center+1; j<=right; j++) { rightBorderSum+=a[j]; if(rightBorderSum>maxRightBorderSum) { maxRightBorderSum=rightBorderSum; e=j; } } return max3(maxLeftSum,maxRightSum, maxLeftBorderSum+maxRightBorderSum);}//该方法我们采用“分治策略”(divide-and-conquer),相对复杂的O(NlogN)的解法//最大子序列可能在三个地方出现,或者在左半部,或者在右半部,//或者跨越输入数据的中部而占据左右两部分。前两种情况递归求解,//第三种情况的最大和可以通过求出前半部分最大和(包含前半部分最后一个元素)//以及后半部分最大和(包含后半部分的第一个元素)相加而得到。long maxSubSum3(const vector &a){ return maxSumRec(a,0,a.size()-1);}//如果a[i]是负数那么它不可能代表最有序列的起点,因为任何包含a[i]的作为起点的子//序列都可以通过用a[i+1]作为起点来改进。类似的有,任何的负的子序列不可能是最优//子序列的前缀。例如说,循环中我们检测到从a[i]到a[j]的子序列是负数,那么我们就可以推进i。//关键的结论是我们不仅可以把i推进到i+1,而且我们实际可以把它一直推进到j+1。long maxSubSum4(const vector &a){ long maxSum=0; long thisSum=0; int t=0; for (int j=0; j maxSum){ maxSum=thisSum; s=t; e=j; } else if(thisSum<0){ thisSum=0; t=j+1; } } return maxSum;}
测试程序:
#include#include #include #include #include #include using namespace std;const long COUNT = 1000;const int MAX_NUM = 200;int Start = 0;int End = 0;bool readFile(vector &input, string fileName){ ifstream infile(fileName.c_str()); if(!infile) { return false; } int s; while(infile >> s) { input.push_back(s); } return true;}bool writeTestData(string fileName){ ofstream outfile(fileName.c_str()); if(!outfile) { return false; } srand((unsigned)time(NULL)); for(int i = 0; i < COUNT; i++) { if(rand() % 2 == 0) { outfile << rand() % MAX_NUM << endl; } else { outfile << ~(rand() % MAX_NUM) <
count = 1000
4135
Time used = 12.87 4135 Time used = 0.06 4135 Time used = 0.00 4135 Time used = 0.00 请按任意键继续. . .count = 2000
8968
Time used = 104.37 8968 Time used = 0.23 8968 Time used = 0.00 8968 Time used = 0.00 请按任意键继续. . .count = 10000 //O(N^3)略去
15302
Time used = 5.88 15302 Time used = 0.02 15302 Time used = 0.00 请按任意键继续. . .count = 100000
33853
Time used = 570.03 33853 Time used = 0.16 33853 Time used = 0.01 请按任意键继续. . .!!!
转载地址:http://wxyhj.baihongyu.com/