LeetCode : 643. Maximum Average Subarray I

[congr]

https://leetcode.com/problems/maximum-average-subarray-i/

[congr]

AC, brute force

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int max = Integer.MIN_VALUE; // !!! negative value included
        for (int i = 0; i <= nums.length - k; i++) {
            int sum = 0;
            for (int j = i, z = 0; z < k; z++) 
                sum += nums[j++];
            max = Math.max (max, sum);
        }

        return (double)max / k;
    }
}

[congr]

O(N)

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int N = nums.length;
        int[] acc = new int[N];
        acc[0] = nums[0];
        for (int i = 1; i < N; i++) acc[i] += acc[i-1] + nums[i];

        int max = acc[k-1];
        for (int i = k; i < N; i++) {
            max = Math.max(max, acc[i] - acc[i-k]); // !! i-k
        }       

        return (double)max / k;
    }
}

[congr]

O(N) takes 9ms, which is faster than 95.95%

[congr]

O(N)

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int sum = 0;
        for (int i = 0; i < k; i++) sum += nums[i];

        double max = sum;
        for (int i = 1; i <= nums.length-k; i++) {
            sum = sum - nums[i-1] + nums[i+k-1];
            max = Math.max(max, sum);
        }

        return max / k;
    }
}