解题思路

这道题目实际上就是求一串数字中，某一段数字和，使其最大
因此，我们可以使用dp来完成
令：dp[i]为以a[i]结尾的最大序列和
则dp[i]可以为 以a[i-1]结尾的最大序列和加上a[i] 与 a[i]中的最大值
即该题的动态转移方程式可以为：dp[i]=max(dp[i-1]+a[i],dp[i]);

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+1e6;
const ll Min=-0x3ffffff;//负∞
ll n,ans=Min;//  【注】：本题涉及到负数，为保证后面的ans=max(ans,dp[i])，ans一开始因赋值为负∞
ll dp[N],a[N];
signed main()
{
    cin>>n;
    for(ll i=1;i<=n;i++)cin>>a[i],dp[i]=a[i];
    for(ll i=2;i<=n;i++)dp[i]=max(dp[i],dp[i-1]+a[i]);//动态转移方程式
    for(ll i=1;i<=n;i++)ans=max(ans,dp[i]);
    cout<<ans;
}