求最大子段和

双指针思想，先前缀和，再在前缀和上跑双指针，前面的指针记录最小值，每次更新pre在 $[1,i]$ 的最小值，用 $pre_i$ 减去之，更新到 $ans$ 即可。复杂度：$O(n)$

vector<ll> pre(n+1);
FOR(i,1,n){cin>>pre[i];pre[i]+=pre[i-1];}
ll mx=0,ans=0;
FOR(i,1,n){//记得看看题目允不允许子段为空
    mx=min(mx,pre[i-1]);
    ans=max(ans,pre[i]-mx);
}
//然后ans即为所求

洛谷P1115 最大字段和

#include<iostream>
#include<vector>
#include<cmath>
#include<set>
#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
#define ET '\n'
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>=(b);i--)
//双向for循环，好像用不到
#define rep(i,a,b) for(ll i=(a);i!=(b)+2*(a<b)-1;i+=2*(a<b)-1)
#define CIN(a) ll a;cin>>a
#define DCIN(a) ld a;cin>>a
#define SCIN(a) string a;cin>>a
#define CA cout<<ans<<ET
#define CY cout<<"YES"<<ET
#define CN cout<<"NO"<<ET
#define max(a,b) ((a>b)?(a):(b))
#define min(a,b) ((a<b)?(a):(b))
#define PP(l,r,CK) *ranges::partition_point(ranges::iota_view((l),(r)+1),(CK))
string ANS[2]={"No\n","Yes\n"};
int M=1e9+7;
inline ll MO(ll x){return (x%M+M)%M;}

void solve(){
    CIN(n);
    vector<ll> pre(n+1,0);
    FOR(i,1,n){cin>>pre[i];pre[i]+=pre[i-1];}
    ll mx=0,ans=-1e18;
    FOR(i,1,n){
        mx=min(mx,pre[i-1]);
        ans=max(ans,pre[i]-mx);
    }
    CA;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //pre();
    //CIN(t);while(t--)
    solve();
    return 0;
}