题意

对于一个子数组求其最大子数组和，现在允许你将数组中的某一段翻转一次，那么翻转后的数组也有一个最大子数组和。问原数组，允许翻转一次能够得到的最大子数组和是多少？

样例

例如3，6，-2，-4，8，5
将前四个反转，得到-4，-2，6，3，8，5，最大子数组和为22（6，3，8，5），
也可以将后四个反转得到3，6，5，8，-4，-2，最大字数和也是22
其他反转方式结果都不大于22；

题解

假设该数组某一段 i 到 j 反转了，现在变成了0…j…i…n-1
那么最终结果应该在哪儿呢。
首先最终的最大子数组和一定不会完全包括 i 到 j 这一段，否则反转没有意义，不反转，最大子数组和也是这一段。
最大子数组和也不会完全不包括 i 到 j 这一段，否则也没有意义

那么最大子数组和一定是要么在 i 到 j的左侧，并且包含反转后的 j 到 i中左侧的一部分，要么就是在 i 到 j 的右侧，并且包含反转后 j 到 i 的右侧一部分

而这两种情况实际上是一一对应的，例如样例中，我们既可以反转左侧，也可以反转右侧，得到的结果是一样的。
设左侧的情况为0…a…i…j…n
存在i<k<j，使得i到j反转后，k到j这部分与a到i-1接上，并且成为最大子数组和
那么必然可以将a到k反转，使得a到i这部分与k到j接上，成为最大子数组和。因此这两种情况是一一对应的。我们只需要考虑一种即可

那么0…n，我们遍历每个i，dp[i]表示以nums[i]开头向右的最大子数组和是多少，那么我们在0~i - 1，找到一个能反转过来接上该子数组的位置即可。
也就是说枚举所有的分割点，尝试在其左侧找到一个反转过来最好的情况。
那么所有分割点得到的最大子数组和最大值就是答案

那么左侧应该让谁翻转过来，才能接上右边部分形成最大的呢，
例如 -6，3，4，-5，（6）。当前求到了-6，以6开始的右侧的最大子数组和已知，那么左侧的三个数该以哪个点反转过来呢。没错以该点为结尾元素的最大子数组应当被翻过来，例如这个样例-6，3，4，-5其中以自己为结尾元素的最大子数组和是3，4和为12，那么3，4就应该被反转过去，和6接上。当然我们不需要真的反转，只需要知道左侧中最大子数组可以被翻过去从而接上右边的数字

因此先求一遍以该位置为起点向右扩展的最大子数组为dp
再从左遍历分割点，同时求左侧的最大子数组和，与对应的dp相加，保存最大值即可

dp[n - 1] = nums[n - 1];
for(int i = n-2;i >= 0;i--){
	dp[i] = nums[i] + max(0,dp[i + 1]);
}
left = nums[0];//我们不需要求出所有的反转后最大子数组和，只需要知道最大的，所以保存一个就可以
leftmaxsum = left;
ans = dp[0];//由于第一个数左侧没东西，不能反转，所以第一个分割点最大子数组和就是以第一个数组开始向右扩展的最大子数组和
for(int i = 1;i < n;i++){
	ans = max(ans,leftmaxsum + dp[i]);
	left = nums[i] + max(0,left);
	leftmaxsum = max(leftmaxsum,left);
}