题目：最大数组和（蓝桥OJ 3260）

问题描述：

解题思路：
        官方：

        总结：使用模拟。排序数组，枚举删除最大个数并推出其删除最小个数 ，即可枚举出每一种可能的区间和，依次比较找最大区间和（使用前缀和求区间和O(1)）即答案。

        注意点：不能使用贪心，即官方首句，因为只能找到局部最优解而非全局最优解。

题解：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 9;
ll a[N], pre[N];//题目数组元素范围大，使用ll

 
int main()
{
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t;cin >> t;
	while(t--)
	{
		
		int n, k;cin >> n >> k;
		for(int i = 1; i <= n; i++)cin >> a[i];
		
		sort(a + 1, a + n + 1);
		
		for(int i = 1; i <=n; i++)pre[i] = pre[i-1] + a[i];
	 
		
		ll ans = 0, q = 0;//q为最小的删除个数(k,q这样定义简化了思路的关系式)***
		while(k>=0)//k为最大的删除个数 
		{
			ans = max(ans, pre[n-k] - pre[q]);
            //区间和最大值。前缀和的优势：快速计算某一段区间和（O(1)）

			q += 2;
			k--;
		}
		
		cout << ans << "\n"; 
	}
  	return 0;
}

知识点：模拟，前缀和