描述

给定一个长度为$nn$的数组，输出加和最大的非空子数组的和。

思路

• 首先考虑数组中的最大值，如果为负数，则最大子数组为该值，否则答案一定大于0
• 当最大值为正时，则最大的子数组肯定不为空，则有以下的解法
  • 暴力，直接O($n^{2}n^2$)暴力枚举各个子数组的和，然后输出最大值即可
  • DP，设$dp[i]dp[i]$表示以第$ii$个元素为结尾的最大子数组的值，则转移公式为$dp[i]=max(\{dp[i-1]+a[i],0\})dp[i]=max(\backslash \{dp[i-1]+a[i],0\backslash \})$,分别代表选这个数和不选这个数的情况

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
typedef long long ll;
int a[MAXN];
ll sum[MAXN];
int main()
{
    int n;
    scanf("%d",&n);
    ll ans=-1e18;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        ans=max(ans,1LL*a[i]);
    }
    if(ans<=0)
    {
        return 0*printf("%lld\n",ans);
    }
    for(int i=1;i<=n;i++)
    {
        sum[i]=max(0LL,sum[i-1]+a[i]);
        ans=max(ans,sum[i]);
    }
    printf("%lld\n",ans);
}

时间复杂度$O(n)O(n)$，空间复杂度$O(n)O(n)$