蓝桥--鸡哥的购物挑战OJ(4169)

题目：

思路：

暴力：

直接枚举所有得偶数区间，找最大值，n2超时

优化：

分类讨论，只要醉倒不重不漏得分类不出意外就能AC了

图中的选择方式很简单了，不做解释了。

AC代码(我的代码可能不比别人简洁，但是我觉得是最好搞懂的了，可能也是太笨了)：

#include <iostream>
#include <algorithm>
using namespace std;typedef long long LL;const int N = 1e5 + 10;LL w[N];
LL sum[N];
int n;int main()
{cin >> n;for (int i = 1; i <= n; i++) cin >> w[i];sort (w + 1, w + n + 1);int num = 0;for (int i = 1; i <= n; i++)if (w[i] > 0)   num++;for (int i = 1; i <= n; i++)   sum[i] = sum[i - 1] + w[i];//防止都是大于0的数，特判一下if (num == n && num & 1){cout << sum[n] - w[1];return 0;}LL res = 0;if (num & 1){int last = w[n - num + 1] + w[n - num];if (last >= 0)res = sum[n] - sum[n - num - 1];else res = sum[n] - sum[n - num + 1];}else res = sum[n] - sum[n - num];cout << res;return  0;
}