CODEWITHSUNDEEP
javaarraysmath
houyichaochao
houyichaochao

Reputation: 11

findMaxAverage with big array failing test cases

Q:Given n integers, find a contiguous subarray with the largest average and length k and output the maximum average.

input: [1,12,-5,-6,50,3], k = 4
output: 12.75
ex: the maxAvr (12-5-6+50)/4 = 51/4 = 12.75

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double[] f = new double[nums.length];//save the max value f[i] with range k from nums[]
        int length = nums.length;
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        if (length == k) {
            return ((double) sum /  k);
        }
        f[k - 1] = (double)sum; // start at f[k-1]
        for (int i = k - 1; i < length - 1; i++) {
            f[i + 1] = f[i] - nums[i - k + 1] + nums[i + 1]; // with dp to find the maxValue in the range k 
        }
        Arrays.sort(f);
        return (double) f[length - 1] / (double) k;
    }
}

Debug

When i debug,i find idea.sh can't solve the big array

Upvotes: 0

Views: 69

Answers (1)

houyichaochao
houyichaochao

Reputation: 11

Thanks i have solve it,the Arrays.sort() expense much time , so i use another method!

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double[] f = new double[nums.length];
        int length = nums.length;
        int sum = 0;
        double pre = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        if (length == k) {
            return ((double) sum /  k);
        }
        f[k - 1] = (double)sum; 
        pre = f[k-1]; // save the max  value
        for (int i = k - 1; i < length -1; i++) {
            f[i + 1] = f[i] - nums[i - k + 1] + nums[i + 1]; 
            if(f[i+1]>pre){
                pre = f[i+1]; // exchange the max value 
            }
        }
        // Arrays.sort(f);   // waste much time!
        return (double) pre / (double) k;
}
}

Upvotes: 1

Related Questions