[LeetCode]Maximum Average Subarray II

这道题不等于maximum subarray sum with length equal to or longer than，因为sum更大的话所包含的元素有可能更多，average有可能更小。但是这道题和其又有一定的关系，我们之后会讲到。
最初尝试用dp来做，dp[i]表示以i结尾的MAS区间(maximum average subarray)，但并没有很好的公式可以推得dp[i + 1]，我们要根据nums[i + 1]的值决定区间是向左扩大还是向右缩小。比如nums[i +１]是负数，我们很可能要向左扩大。但是对于有的只是为了满足长度k而包括进去的部分（实际去除我们可以让avg变大），我们很可能需要向右缩小，所以归根结底还是需要n^2的时间。
答案给了我们一个binary search的解法，和空间上(index)的binary search，我们从值域上binary search。也就是说，取一个值，看array能不能满足这个avg，能的话继续增加，否则减小。这种解法在其他类型的题目上也会有其他的应用。在这里我们用这种解法，所以问题转化为，给定一个值m，我们判断在数组中是否存在平均值大于等于m的长度大于等于k的空间。这么想还是有点不好做，所以我们继续变，数组中每个值减去avg，问题转化为，判断数组是否存在长度大于等于k的subarray，sum大于等于0。也就是说，我们成功把这一题转化为我们开始提到的问题，我们求数组中长度大于等于k的subarray sum的最大值，如果其大于等于0，我们之前的所有问题都成立。
这和我们之前解决的max subarray sum问题很像，都可以转化成presum的问题来做(best time to buy and sell stocks)，区别在于，之前我们要维护到i之前的presum的最小值，这里我们只要考虑到i - k之前的presum最小值，做法是类似的。时间复杂度O(n * logn)，常数空间复杂度，代码如下：

	class Solution {
	public:
	double findMaxAverage(vector<int>& nums, int k) {
	int len = nums.size();
	double lo = INT_MAX, hi = INT_MIN;
	for(auto& num : nums)
	{
	lo = min(lo, static_cast<double>(num));
	hi = max(hi, static_cast<double>(num));
	}
	while(hi - lo >= 0.00001)
	{
	double mid = lo + (hi - lo) / 2;
	if(check(nums, mid, k))
	lo = mid;
	else
	hi = mid;
	}
	return lo;
	}
	private:
	bool check(vector<int>& nums, double avg, int k)
	{
	vector<double> preSum(nums.size());
	for(int i = 0; i < nums.size(); ++i)
	preSum[i] = i? preSum[i - 1] + nums[i] - avg: nums[i] - avg;
	double globalMax = preSum[k - 1], minSum = 0;
	if(globalMax >= 0)return true;
	int i = k;
	while(i < nums.size())
	{
	minSum = min(minSum, preSum[i - k]);
	double localMax = preSum[i] - minSum;
	globalMax = max(globalMax, localMax);
	++i;
	if(globalMax >= 0)return true;
	}
	return false;
	}
	};

view raw Maximum Average Subarray II.cpp hosted with ❤ by GitHub