「最大子段和」题解

首先看一眼标签。能不能暴力？好像不行，如果数据大于时可能会超时，那就只能打正解了。

最大子段和问题，首先要遍历数组。

在遍历时，如果前面的子段和是负数那么重新开始‌一个新的子段（只包含），否则延续‌之前的子段。（将加入到之前的子段中）

为什么如果前面的子段和是负数要重新开始‌一个新的子段？因为如果继续累加会导致答案错误，不如从当前位置重新开始。

那么可以推出动态转移方程：

那么这道题就完成了。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=1e7+7;//冷知识：如果数组长度是奇数那么会更快一点 
int a[N];
int n;
signed main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    //初始化
    int maxn=a[0];//最大子段和
    int ans=a[0];//当前子段和
    for(int i=1;i<n;i++) {
        //比较当前子段和和当前元素，看看是否需要重新开始
        ans=max(a[i],ans+a[i]);
        //更新最大子段和
        maxn=max(maxn,ans);
    }
    cout<<maxn;
    exit(0);
}

AC Code

暂无评论