两种方法的题解

方法1思路：
看到这道题，第一眼就知道是DP，因为题目中要求的子段是连续且非空的，所以我们可维护一个DP数组，对于每一个元素，实则有两种选择：将其并入上一个元素所在子段或将其作为另一个子段的首个元素

代码呈现：

#include<bits/stdc++.h>
using namespace std;
int n;
long long a[200005],dp[200005],ans;
int main()
{
    ans=-1e15;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(i==1)dp[i]=a[i];
        else dp[i]=max(a[i],dp[i-1]+a[i]);
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}

方法2思路：
我们也可以运用前缀和的思路进行解题，即一个从i到j的子段的总和可以由从1到j的子段的总和减去
从1到i的子段的总和得出。对于每一个元素i，我们需要查找以他为结尾的子段中和最大的，这里就可以使用前缀和优化。因为从第一个元素至第I个元素的值是固定的（定义sum[i]为前i个元素的和），所以问题转化为：在第1至i-1个元素中找出最小的一个（被减数固定，自然是减数越小越好），而这个问题也可以用前缀和解决（定义pre[i]为前i个元素中从1到i的总和最小的）。

代码呈现

#include<bits/stdc++.h>
using namespace std;
int n;
long long a[200005],sum[200005],pre[200005],ans;
int main()
{
    cin>>n;
    memset(pre,1e9,sizeof(pre));
    ans=-1e15;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        pre[i]=min(pre[i-1],sum[i]);
        ans=max(ans,sum[i]-pre[i-1]);
    }
    cout<<ans;
    return 0;
}