如题：给一个有n个整数的数组a[]，给一个m，要你求出在数组中最多取m个连续的数能获得的最大和。

题目链接：https://acm.uestc.

您的思路应是正确的，可这个效率不足以通过这道题唉。

刚刚想到方法解决了。
我预处理了前缀和，然后用线段树维护前缀和的最小值。
以第i个元素为结尾的最大连续序列和就是：max( sum[i] - sum[j] ) （其中sum[j]是i的前m个元素中前缀和的最小值）
这样算法的时间复杂度是O(nlogn)的，能跑得动。

通过代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const long long inf = 0x3f3f3f3f3f3f3f3fLL;
long long a[N], sum[N], tree[N<<2];

void pushup(int rt)
{
    tree[rt] = min(tree[rt<<1], tree[rt<<1|1]);
}

void build(int l, int r, int rt)
{
    if (l == r){
        tree[rt] = sum[l];
        return;
    }
    int mid = (l+r) >> 1;
    build(l, mid, rt<<1);
    build(mid+1, r, rt<<1|1);
    pushup(rt);
}

long long query(int L, int R, int l, int r, int rt)
{
    if (L <= l && r <= R){
        return tree[rt];
    }
    int mid = (l+r) >> 1;
    long long ans = inf;
    if (L <= mid) ans = min(ans, query(L, R, l, mid, rt<<1));
    if (R > mid) ans = min(ans, query(L, R, mid+1, r, rt<<1|1));
    return ans;
}

signed main(void)
{
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    long long mx = -inf;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        mx = max(mx, a[i]);
        sum[i] = sum[i-1] + a[i];
    }
    if (mx <= 0){
        cout << mx << endl;
        return 0;
    }
    build(0, n, 1);
    long long ans = 0;
    for (int i = 1; i <= n; ++i){
        int s = (i - m >= 0) ? i-m : 0;
        ans = max(ans, sum[i]-query(s, i, 0, n, 1));
    }
    cout << ans << endl;
    return 0;
}