简要题意:给一串数,找连续两串使其和最大
传统求最大子串的方法不能保证两段不相交,因此考虑多开个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; }