Massive Algorithms: LintCode 617 - Maximum Average Subarray

Given an array with positive and negative numbers, find the maximum average subarraywhich length should be greater or equal to given length k.

Notice

It's guaranteed that the size of the array is greater or equal to k.

Example

Given nums = [1, 12, -5, -6, 50, 3], k = 3

Return 15.667 // (-6 + 50 + 3) / 3 = 15.667

http://www.jiuzhang.com/solutions/maximum-average-subarray/

    public double maxAverage(int[] nums, int k) {
        // Write your code here
        double l = Integer.MAX_VALUE, r = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] < l)
                l = nums[i];
            if (nums[i] > r)
                r = nums[i];
        }
        
       
        while (r - l >= 1e-6) {
            double mid = (l + r) / 2.0;

            if (check_valid(nums, mid, k)) {
                l = mid;
            }
            else {
                r = mid;
            }
        }

        return l;
    }
    
    private boolean check_valid(int nums[], double mid, int k) {
        int n = nums.length;
        double min_pre = 0;
        double[] sum = new double[n + 1];
        sum[0] = 0; 
        for (int i = 1; i <= n; ++i) {
            sum[i] = sum[i - 1] + nums[i - 1] - mid;
            if (i >= k && sum[i] - min_pre >= 0) {
                return true;
            }
            if (i >= k)
                min_pre = Math.min(min_pre, sum[i - k + 1]);
        }
        return false;
    }

http://blog.csdn.net/gqk289/article/details/68952421

求值问题很多可以用二分，初始beg & end是数组的最小和最大值。

二分另一点在于valid函数。本题中为给定一个mid，判断是否存在长度大于等于k且平均值大于等于mid的子数组。sum[i]保存nums[i] - mid的和。如果sum[i] - min_pre >= 0的话说明当前子数组的平均值大于等于mid

http://blog.csdn.net/qq_34153219/article/details/56298842
一开始用了最简单的遍历循环法，时间复杂度为O(N^2)，然后被提醒超时，上网查了之后做了一个小改动，用一个sum数组存储num[0]到num[i]的总和，这样算num[i]到num[j] 只要算sum[j]-sum[i]就好了。

double maxAverage(vector<int>& nums, int k){
double result;
int i,j,num;
int vectorLength=nums.size();
double tmp[vectorLength];
tmp[0]=0;
for(i=1;i<vectorLength+1;i++){
tmp[i]=tmp[i-1]+nums[i-1];
}
result=tmp[vectorLength]/vectorLength;
for(j=vectorLength;j>=k;j--){
for(i=0;i<vectorLength-k+1;i++){
if(j-i>=k&&(tmp[j]-tmp[i])/(j-i)>result)
result=(tmp[j]-tmp[i])/(j-i);
else if(j-i<k)
break;
}
}
return result;
}

个人理解：

1、一个数组的子数组的最大平均数一定在数组的最大值和最小值之间，所以二分法的第一步限定average位于[min,max]之中。

2、接下去要做的就是不断的缩小范围，直至max-min足够小（如1e-6），那我们就得到了想要的结果。

缩小范围的思想如下：

每一轮设置mid=(min+max)/2，然后将原数组中的每一个数减去这个mid，如果能找到（经过提醒，改正为：大于等于）k个相邻数的总和大于0的情况，那么说明最终结果一定比这个mid要更大，限定下一轮寻找范围在[mid,max]之中。反之在限定在[min,mid]之中。

那么在实际算法中我们需要解决的关键一步就是，如何判断“有（大于等于）k个相邻数的总和大于0的情况存在”。

首先，我们可以用sum数组来存储减掉mid值的原数组的各总和（sum[i]存储num[0]-mid到num[i-1]-mid的总和），当sum[i]存储的总和个数超过k时（即i>k），也就是说我们保证了这个子数组的长度达到k后，可以砍掉之前一些拖后腿的数。这些拖后腿的数在上述链接的代码中是用min_pre来实现的。当之前拖后腿的数值小于min_pre时，更新min_pre=sum[i - k + 1]。sum[i]存储的是num[0]~num[i-1]减去mid的总和，而min_pre存储的是num[0]~num[k]减掉mid的总和，这样sum[i]-min_pre得到的是sum[k+1]~sum[i-1]，它所记录的总和个数也就是到num[i]为止能够找到的最大平均数 子数组的长度。

LintCode 617 - Maximum Average Subarray

Notice

Labels

Popular Posts