题解 | #Maximum sum#

简要题意：给一串数，找连续两串使其和最大

传统求最大子串的方法不能保证两段不相交，因此考虑多开个b数组记录以它开头的最大子串

令a[i]为以i结尾的子串最大和，b[j]为以j开头的子串最大和，这样ans=max(a[i]+b[j])，这样需要O(n^2)

下面考虑将其优化成O(n):

法一：(官方题解)将a[i]更新成a[i]是以0.....i的子串最大和，b[j]为以j.......n-1开头的子串最大和，这样ans=max(a[i]+a[i+1])
链接：https://www.nowcoder.com/ta/acm-solutions/review?tpId=20&tqId=14372&query=2479&asc=true&order=&page=1

法二：用i从前往后迭代，一路记下a[i]的最大值，每次将之前走过a[i]的最大值和当前遍历到的b[j]相加

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int n;
int x[50005];
int a[50005];
int b[50005];
inline int read()
{
    char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
    int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
    if(nega==-1) return -ans;
    return ans;
}
int main(){
    int T;
    T=read();
    while(T--){
        n=read();
        for(int i=0;i<n;i++){
            x[i]=read();
            a[i]=b[i]=x[i];
        }    
        for(int i=1;i<n;i++){
            a[i]=(a[i-1]>0)?a[i-1]+a[i]:a[i];
        }

        for(int i=n-2;i>=0;i--){
            b[i]=(b[i+1]>0)?b[i+1]+b[i]:b[i];
        }

        int ma=-0x3f;
        int ans=-0x3f;
        for(int i=0;i<n-1;i++){
            ma=max(ma,a[i]);
            ans=max(ans,ma+b[i+1]);
        }
        cout << ans << "\n";
    }
    return 0;
}