分治初解

分治是一种基于二分的解题思路
分治字面理解即为分开治理
以题目最大子段和为例子
(题目：最大子段和)
(PS：请先看题)
题目样例：
7
2 -4 3 -1 2 -4 3
用分治思想来看
我们需要先把这个数列二分一下
得到：
2 -4 3 -1 和 2 -4 3
接着分别从两个新数列的开头向后走
第一个数列从-1开始向左走，每次更新最大值（左边情况）
第二个数列从2开始向右走（右边情况）
将第一个数列和第二个数列的最大值加起来得到中间向两边找的情况，且必定为最优的可能答案（想想为什么）

代码实现：

#include <bits/stdc++.h>

#define ll long long//把long long 用 ll 代替 

using namespace std;

const int INF = 0x7fffffff;//设定最大值，应为有负数 

ll a[1000001], ans = -INF, n;

void zdh(ll l, ll r) {
	if(l >= r) return;
	ll m = l + (r -l) / 2;//二分 
	zdh(l, m);//递归左边 
	zdh(m + 1, r);//递归右边 
	ll a1 = 0, a2 = 0, ans1 = -INF, ans2 = -INF;//a1, a2求和， ans1, ans2更新答案 
	for(int i = m; i >= l; i --) {//向左找 
		a1 += a[i];//加起来 
		ans1 = max(a1, ans1);//更新 
		ans = max(ans, ans1);//更新最后答案 
	}
	for(int j = m + 1; j <= r; j ++) {//向右找 
		a2 += a[j];
		ans2 = max(a2, ans2);
		ans = max(ans, ans2);
	}
	ans = max(ans1 + ans2, ans);//更新中间情况 
}

int main() {
	cin >> n;
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
	}	
	zdh(1, n);
	cout << ans ;
	return 0;
}