前缀和（优化算法）

对于程序来说，看到范围，或者明确的次数，或不确定多个，就用循环结构。
遇到能或不能用分支结构。
【数组找最值】打擂台；排序后输出最后一个；
输出数组第一个：sort(a,a+n,greater<int>())从大到小
【数组相邻两个数的和的最大值】不能排序，自己做一下。

6 3        
3 6 4 1 5 2

#include <bits/stdc++.h>
using namespace std;//6 3
//3 6 4 1 5 2
int main() {int n, m;cin >> n >> m;int a[n];for (int i = 0; i < n; i++) {cin >> a[i];}int max = 0;//前m个数的和for (int i = 0; i < m; i++) {max += a[i];}//for (int i = 0; i <= n - m; i++) {int t = 0;for (int j = i; j < i + m; j++) {t += a[j];cout << a[j] << "+";}cout << "=" << t << endl;if (max < t)max = t;}cout << max;return 0;}

【任意m个相邻数和最大的那组】输出结果。自己做一下。

【前缀和来解题】优化，数组连续区间求和就用它。自己做一下。
核心思想：通过减法获取连续区间。 ①②③④⑤⑥⑦⑧⑨⑩
a[0] = ① 
a[1] = ① + ②
a[2] = ① + ② + ③
a[3] = ① + ② + ③ + ④
...
a[n] = ① + ② + ③ + ④ + ... + 第 n + 1 个数

观察
① + ② ==> a[1]
② + ③ ==> a[2] - a[0]

思考
获取第 i 位第 i + 1位的数 ==>
a[i] = ① + ② + ③ + ④ + ... + 第 i + 1 个数
a[i - 1] = ① + ② + ③ + ④ + ... + 第 i 个数
a[i - 2] = ① + ② + ③ + ④ + ... + 第 i - 1 个数
变形
a[i] = ① + ② + ③ + ④ + ...+ 第 i - 1 个数 + 第 i 个数 + 第 i + 1 个数
将
a[i] + a[i+1] = a[i] - a[i-2]拓展
获取m个数的区间 ==> a[i] - a[i-m]  从当前数开始往前数m个数
前缀和标准输入：

int n;
cin >> a[0];
int a[n];
cin >> a[0];
for(int i = 1; i < n; i++){int t;cin >> t;a[i] = a[i-1] + t;
}

//可以减少一层循环

#include <bits/stdc++.h>
using namespace std;int main() {int n, m;cin >> n >> m;int a[n];for (int i = 1; i < n; i++) {int t;cin >> t;a[i] = a[i - 1] + t;}int max = a[m - 1];for (int i = m; i < n; i++) {int t = a[i] - a[i - m];if (max < t)max = t;}cout << max;return 0;}