Monday, July 17, 2017

LeetCode 643: Maximum Average subarray


/**
 * Problem: Given an array consisting of n integers, find the contiguous subarray of given length k that has 
 * the maximum average value. And you need to output the maximum average value.
 */
public class MaximumAverageSubarray643 {
    /*
    At every character position calculate sum of next k characters and compare it with the max sum seen so far
    at the end return average
     */
    public double findMaxAverage(int[] nums, int k) {
        if(nums == null || nums.length < k)
            return 0;
        int length = nums.length -1;
        double maxSum = Integer.MIN_VALUE;
        for(int i =0 ; i < nums.length-k+1; i++){
            int localSum = 0;
            for(int j = i ; j < i+k ;j++){
                localSum = localSum + nums[j];
            }
            maxSum =Math.max(maxSum,localSum);
        }
        return maxSum/k;
    }
}

No comments:

Post a Comment