Straightforawrd Java O(N) solution with explanation...

  • 0
    public double findMaxAverage(int[] nums, int k) {
            if(k>nums.length) return (double)0;
            double sum = 0;
            for(int i = 0;i<k;i++){ // get the sum from 0 to k-1th num
                sum += nums[i];
            double pre = sum - nums[0];// the sum from 1th to k-1th num could be used in next time when we calculate the sum from 1 to kth num
            double max = sum/k;
            for(int i = 1;i+k-1<nums.length;i++){
                sum = pre +nums[i + k -1];// use pre to plus the last num within these k nums
                max = Math.max(max,sum/k);
                pre = sum - nums[i];// update the pre which could be used in next caculation
            return max;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.