题解 P1115 【最大子段和】

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;

接着比较三个之中最大的,选择这一个输出即可

#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快,判断大小

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;
}