差分+前缀和习题集

（luogu题号）

P6568 [NOI Online #3 提高组] 水壶

思路分析

        前缀和优化问题。

        其实题意就是让你求有k+1个数的区间和最大值，那么直接前缀和优化，就可以通过本题。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;
int a[N];

int main(){
	int n,k,mx = -1e9; cin >> n >> k;
	k++;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		a[i] += a[i-1];
	}
	for(int i = 1; i <= n-k+1; i++){
		mx = max(mx,a[i+k-1]-a[i-1]);
	}
	cout << mx << endl;
	return 0;
}

P6625 [省选联考 2020 B 卷] 卡牌游戏

思路分析

        前缀和思想的一道题。

        这个其实就是让你求左边两张牌合并之后大于0就继续合并的求最大值的，有点像贪心的思想，左边能合并且合并后大于0