1.最大的和

题目描述

输入长度为 n 的数组 A ，求数组 A 中所有长度为 m 的区间里，区间和最大的那个区间的区间和。(数组中可能出现负数)

输入格式

第一行两个整数 n 和 m 第二行给出 n 个整数，第i个整数代表Ai 1<=n<=10^5，1<=m<=n，-10000<=Ai<=10000

输出格式

输出一行答案，最大的区间长度为 m 的区间和

样例

Input

5 3
2 5 -4 10 3

Output

11

样例解释

样例输入1的解释：给定数组A=[2, 5, -4, 10, 3]，区间长度为3的所有子数组为 [2, 5, -4], [5, -4, 10], [-4, 10, 3]，其中区间和最大的子数组为 [5, -4, 10]，区间和为11

数据范围

1<=n<=10^5，1<=m<=n，-10000<=Ai<=10000

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int sum[N],a[N];
int n,m,ans=INT_MIN,t;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>t;
		sum[i]=sum[i-1]+t
	for(int i=1;i<=n;i++)
	{
		ans=sum
     /*到这儿不会了，求代码*/
	}
	return 0;
}

前缀和没听讲