• 方法1:处理当前位置之前的前缀和的最小值,每次计算当前位置到这个位置的子段和即可
    代码:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    const ll inf=1e9+1;
    void solve(){
      ll n; cin>>n;
      vector<ll> a(n+1);
      for(int i=1;i<=n;i++) cin>>a[i];
      ll minn=0,now=0,ans=-inf;
      for(int i=1;i<=n;i++){
        now+=a[i];
        ans=max(ans,now-minn);
        minn=min(minn,now);
      }
      cout<<ans<<endl;
    }

注意几个细节,首先minn存储的是到目前为止的最小值,应该默认为0,在所有数字全为正数的情况下,表示空串的前缀和为0.先计算ans再计算minn,这是因为不能产生空串,保证取的是前面的前缀和.

  • 方法2:传统dp法:

代码:

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long a,maxn=LONG_LONG_MIN,sum=0,n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a; sum+=a;
        if(sum<a) sum=a;
        if(sum>maxn) maxn=sum;
    }
    cout<<maxn<<endl;
}

思路:如果当前值比前面求的和还要大,那么放弃前面的求和,直接新开一段

变形:求子段%p意义下的最大子段和

依旧先计算前缀和(在%p意义下),前面的前缀和更小,可能是两个和还没相差p,要是当前的更小,大概率是超过了p,翻上去了,所以要考虑两个位置,前缀最小值和第一个比当前数字大的前缀和值.

代码略,自己写去,up懒