题目链接：戳一戳

题目：

做法：

首先要知道

不循环数组得最大子段和解法   戳一戳 链接

然后呢

循环数组的最大子段和有两种情况：

一是 和正常数组一样  求出最大字段和  ans1

二是  最大字段和不连续    a1+a2=sum    (后边+前边) 

这个时候就要把中间那段求出来 用总和减去 才是最大子段和

那么我们当然希望中间那段的值越小越好了  最小得到的子段和才是最大

所以我们求这个数组的最小子段和   怎么求最小子段和呢？  

（数组所有数字乘上 -1    然后按照求最大字段和的办法  求出最大字段和 

再把结果乘-1  就是最小子段和了）

用总和减去求得的最小子段和   得到的就是第二种情况的最大子段和  ans2

由于我们并不确定是那种情况  所以我们两种都算出来  取其中大的那个

ans=max（ans1，ans2）

代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
ll a[maxn];
ll b[maxn];
ll dp[maxn];
const ll INF=8e18;
ll n,sum;
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){scanf("%lld",&a[i]);sum+=a[i];}
    for(int i=1;i<=n;i++)b[i]=-a[i];
    memset(dp,0,sizeof(dp));
    ll maxx=0;
    for(int i=1;i<=n;i++){
        dp[i]=max(a[i],dp[i-1]+a[i]);
        maxx=max(dp[i],maxx);//记录最大连续子段和
    }
    memset(dp,0,sizeof(dp));
    ll m=0;
    for(int i=1;i<=n;i++){
        dp[i]=max(b[i],dp[i-1]+b[i]);
        m=max(dp[i],m);
    }
    if(sum+m>maxx)maxx=sum+m;
    printf("%lld\n",maxx);
}