题解 P1115 【最大子段和】

//oier蒟蒻题解，大佬见笑 进入正题，分治解法，可能与前面•的•有相似，纯属巧合： 分成3组： 1.当最大子段和包含中点时，f<i<mid<j<l,即求出区间[i..mid]与区间[mid+1..j]，将其相加即可; 2.f<i<j<mid,递归从f到mid 3.mid<i<j<l，递归从mid+1到l； 接着比较三个之中最大的，选择这一个输出即可 ```cpp #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<cctype> //头文件 #define For(i,j,n) for(int i=j;i<=n;++i) #define FOR(i,j,n) for(int i=j;i>=n;--i) #define minl -19260817 //宏定义，不耗费空间,写起来方便 using namespace std; int a[200000+10];//定义数组 inline int read(){ int X=0,w=0; char ch=0; while(!isdigit(ch)) {w|=ch=='-';ch=getchar();} //判断是否为负数与数字 while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); //读入数字 return w?-X:X;//如果是负数返回负的，否则返回正的 ``` }//读入优化，比scanf更快 inline int Max( int a , int b) { return a > b ? a : b ;}//比STL快，判断大小 ```cpp int dg(int f,int l){ if(f==l)return a[f];//分治终止条件：如果只有一个数，则这个数一定最大 int mid=(f+l)>>1,sum=0,maxl=minl,maxn=minl;//>>是卫衣运算符，是将这个数除2并且取整 FOR(i,mid,f){//从mid到f找最大，注意要从mid开始，i不断自减 sum+=a[i];//累加 maxl=Max(sum,maxl);//如果这一段更大，更新左子段最大值 } sum=0;//计数器清零 For(i,mid+1,l){//从mid+1到l找最大 sum+=a[i]; //累加 maxn=Max(sum,maxn); //如果这一段更大，更新右子段最大值 } return Max(Max(dg(f,mid),dg(mid+1,l)),maxl+maxn);//取3种情况中最大，并且返回 } int main(){//主函数 ios::sync_with_stdio; int n=read(); For(i,1,n)a[i]=read();//读入 cout<<dg(1,n); return 0; } ```