题解 P1115 【最大子段和】
vivarock
2017-12-20 13:05:07
//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;
}
```