动态规划：环形子数组的最大和 - 动态规划 - 数据结构与算法 | Aayu Yain = 学无止境 = 世界上大部分事，都没太大意义。真理与热爱除外

# 题目描述

真的是不得不服，我只能想到双重 for 循环滚动求解环形数组，结果果不其然，时间是超时的，我真的想不出其他思路了，只能去求助官方题解了，谁知官方题解不说人话，就在我继续逛评论区时，看到惊为天人的思路，真的是不得不服，再次感叹呐

直接两种情况，1：最大数组和在中间，和平时一样解法 2：最大数组和是跨越头尾，回头了，麻烦第二种，从两边出发往中间靠拢必须都是最大，那就说明中间段就是最小，找最小不就行了

学无止境，自己要学的东西还有很多啊～

	class Solution {
	public:
	int maxSubarraySumCircular(vector<int>& nums) {
	// 情况 1 最大段就在中间
	int prev = 0, mx = nums[0];
	for (const int &x : nums) {
	prev = max(x, prev + x);
	mx = max(mx, prev);
	}
	prev = 0;
	// 情况 2 最大段跨越首位，那就说明最小段在中间，太牛逼了这个想法，真的顶礼膜拜
	int sum = 0, mi = nums[0];
	for (const int &x : nums) {
	prev = min(x, prev + x);
	mi = min(mi, prev);
	sum += x;
	}
	int mx2 = sum - mi;
	// 返回最大值，我还是笨呐，这里要判断 mx2 是否为 0 了，如果为 0，就表示全是负数，那就返回 mx
	return mx2 == 0 ? mx : max(mx, mx2);
	}
	};