最大子串和(三种方法实现）

如果错误或不周，请指教谅解，感谢你的观看

题目大意 :对于一个数组a，有n个整数，求出最大的子串和，子串中的元素数量至少为1个

举个例子，求下列最大的子串和

6
1 -2 5 2 -3 5   

输出为 9

2

-1 -2

输出为 -1

下面提供代码，代码中自含解释 （就不提供主函数，可能会影响观感)

第一种方法：

typedef long long ll;
int n;
ll a[N], dp[N];
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    dp[1] = a[1];
    ll num = a[1]; // 初始化 避免全为负数的情况
    for (int i = 1; i <= n; i++)
    {
        dp[i] = max(a[i], a[i] + dp[i - 1]); // dp[i]表示到当前位置的最大子串和
        num = max(num, dp[i]);
    }
    cout << num;
}

 第二种方法：

typedef long long ll;
int n;
ll a[N];
void solve()
{
    cin >> n;
    ll ma = LONG_MIN, mi = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] += a[i - 1];        // a[i]表示到当前位置的子串和
        ma = max(ma, a[i] - mi); // a[i]-mi得到答案
        mi = min(mi, a[i]);      // mi表示最小的子串和
    }
    cout << ma;
}

第三种方法：

int n;
ll a[N];
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    ll num = a[1], sum = 0; // num进行初始化 避免全为负数的情况
    for (int i = 1; i <= n; i++)
    {
        sum += a[i];
        if (sum > num)
            num = sum;
        if (sum < 0)
            sum = 0; // 两个if顺序不能换
    }
    cout << num;
}

个人喜欢最后一种

对于全为负数的情况，上面三种方法依然可行

再次感谢观看!!!