[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)，常数空间复杂度，代码如下：