子数组最大连续和

难度：2星

解法1 动态规划

定义 $dp[i]dp[i]$ 为前 $ii$ 个数中，以第 $ii$ 个数结尾的子数组最大连续和。

于是有转移方程：

$dp[i]=max(dp[i-1]+a[i],a[i])dp[i]=max(dp[i-1]+a[i],a[i])$

其中，前面部分代表选择前面的区间的最大值，后面部分代表直接选择a[i]。

最终答案是所有的 $dp[i]dp[i]$ 的最大值。

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

解法2 贪心

我们用一个变量维护到当前位置的最大和，当加到负数的时候我们就可以把它置为0，因为显然负数再往后加会让答案变小。最终维护这个变量的最大值即可。

这种做法需要特判所有数均为负数的情况。这种情况直接输出绝对值最小的那个负数就行了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll dp[101010];
ll a[101010];
int main(){
    int n,i;
    cin>>n;
    int jud=0;
    for(i=1;i<=n;i++){cin>>a[i];if(a[i]>=0)jud=1;}
    if(!jud){
        ll res=-1e9;
        for(i=1;i<=n;i++)res=max(res,a[i]);
        cout<<res;
        return 0;
    }
    ll res=a[1],sum=max(0LL,a[1]);
    for(i=2;i<=n;i++){
        sum=max(0LL,sum+a[i]);
        res=max(res,sum);
    }
    cout<<res;
}