最大连续和

ntwuhui · 2018-12-16 16:00:28 · 题解

方法一：暴力求解

枚举左端点，枚举右端点，计算该范围内的值，并打擂台。

时间复杂度：O(n^3)

#include <bits/stdc++.h>
using namespace std;
const int MaxN = 50000;
const int INF = 2147483647;
int a[MaxN+1];

int main()
{
    int n,ans=-INF;
    cin >> n;
    for (int i=1;i<=n;i++) cin >> a[i];
    for (int i=1;i<=n;i++) // 枚举左端点
        for(int j=i;j<=n;j++;) // 枚举右端点
        {
            int s=0;
            for (int k=i;k<=j;k++) s+=a[k];
            ans = max(ans,s);
        }
    cout << ans << endl;
    return 0;
}

方法二：前缀和优化

计算该数组的前缀和数组s：s[0]=0, s[i]=s[i-1]+a[i]

这样，最内层求和可以用前缀和的差直接O(1)计算得到。

时间复杂度：O(n^2)

#include <bits/stdc++.h>
using namespace std;
const int MaxN = 50000;
int a[MaxN+1],s[MaxN+1];
const int INF = 2147483647;

int main()
{
    int n,ans=-INF;
    cin >> n;
    for (int i=1;i<=n;i++) 
    {
        cin >> a[i];
        s[i]=s[i-1]+a[i];
    }
    for (int i=1;i<=n;i++) // 枚举左端点
        for(int j=i;j<=n;j++;) // 枚举右端点
            ans = max(ans,s[j]-s[i-1]);
    cout << ans << endl;
    return 0;
}