c语言编译的最大子序列求和问题

Question

定（可能有负数）整数序列A1, A2, A3..., An，求这个序列中子序列和的最大值。（为方便起见，如果所有整数均为负数，则最大子序列和为0）。

Answer 1

1. 代码已全部改成C风格，
2. 代码已C测试通过
3. 已经加上题解和思路
4. 又不会可以记叙文

---

可以参考我的：https://blog.csdn.net/qq_33957603/article/details/80554648

以及代码提交（验证正确）地址：http://www.joyoi.cn/problem/tyvj-1305

###传统的做法是，枚举(只要对的话就够了
如果n<=10^3，我们很容易写出枚举（s是前缀和，区间[l,r]的和就是s[r]-s[l-1]。枚举l,r即可。

 #include<stdio.h>
#define maxn 300010
#define max(a,b) (a>b?a:b)
int a[maxn], q[maxn];
long long s[maxn], ans;
int main(){
    int n, m;
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++){
        scanf("%d",&a[i]);  s[i]=s[i-1]+a[i];
    }
    for(int i = 1; i <= m; i++)//枚举长度
        for(int j = i; j <= n; j++)//枚举r
            ans = max(ans, s[j]-s[j-i]);//可以算出l
    printf("%d\n",ans);
    return 0;
}

###如果需要更快的，，，可以考虑用单调队列

• 如果右端点是i，那么就转为求一个左端点j属于[i-m,i-1]并且s[j]最小。并且j越靠近m一定是越优的（在后面更不容易超过m。
• 所以选择集合一定是，“下标位置递增，对应前缀和s也递增”的序列，我们可以用队列保存这个序列。

#include<stdio.h>
#define max(a,b) (a>b?a:b)
#define maxn 300010
using namespace std;
int a[maxn], q[maxn];
long long s[maxn], ans;
int main(){
    int n, m;
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++){
        scanf("%d",&a[i]);  s[i]=s[i-1]+a[i];
    }
    int l = 1, r = 1;
    q[l] = 0; //save j
    for(int i = 1; i <= n; i++){
        while(l<=r && q[l]<i-m)l++;
        ans = max(ans, s[i]-s[q[l]]);
        while(l<=r && s[q[r]]>s[i])r--;
        q[++r] = i;
    }
    printf("%d\n",ans);
    return 0;
}