题目大意:给一个序列,求它的最大子序列和,该子序列的起点,终点。
O(n)的做法.-容易标记起点终点!思想也很简单。
只要前面的加起来为负数了,就开始新的一段子序列和的计算。
4 0 0 2 0 —— 2 1 3
6 2 7 -9 5 4 3 —— 12 1 6
4 0 0 -1 0 —— 0 1 1
7 -1 -2 -3 -2 -5 -1 -2 —— -1 1 1 全部为负数时!
6 -1 -2 -3 1 2 3 —— 6 4 6
----------------------------------------------------------------------------------
增加一组测试数据:
5 -3 -2 -1 -2 -3 —— -1 3 3
#include<iostream> using namespace std; int a[100010]; int i; int N; int max_start,max_end,start; int count=1; int maxSubSum(const int *a) { int sum,max; sum=max=a[1]; //一定要初始化为第一个 start=max_start=max_end=1; //都初始化为第一个. for(int j=2;j<=N;j++) //从第二个开始枚举 { /*一旦前面和为负数,则从新的起点又开始算子序列和!*/ if(sum+a[j]<a[j])//(首先只有sum为负数才可能满足条件)然后分两种情况,一个a[j]>=0,或者a[j]<0; { sum=a[j]; //例:-2 -1 1 只有加到一个正数才会 不满足这个条件! start=j; //把sum 与start又从新起点j开始 } else sum+=a[j]; //否则一直加 if(sum>max) //当大于max { max=sum; //记录下所需要的 最大值 ,起点,终点. max_start=start; max_end=j; } } return max; } int main() { int T; cin>>T; while(T--) { cin>>N; for(i=1;i<=N;i++) cin>>a[i]; cout<<"Case "<<count++<<":"<<endl; cout<<maxSubSum(a); if(T!=0) cout<<" "<<max_start<<" "<<max_end<<endl<<endl; else cout<<" "<<max_start<<" "<<max_end<<endl; } return 0; }
O(nlogn)二分的做法-没有记录起点,终点.(只是二分的模板,与题无关)
(参考他人)
long max3(long a, long b, long c) { if (a < b) { a = b; } if (a > c) return a; else return c; } //递归法,复杂度是O(nlogn) 难以记录 起点,终点!!!!!!!! long maxSumRec(int* 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; } //求出以右边对后一个数字结尾的序列最大值 long maxRightBorderSum = 0, rightBorderSum = 0; for (int j = center+1; j <= right; j++) { rightBorderSum += a[j]; if (rightBorderSum > maxRightBorderSum) maxRightBorderSum = rightBorderSum; } cout<<"左="<<left<<"右="<<right<<endl; cout<<"max3="<<max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum)<<endl; return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum); }