# Maximum Average Subarray II

This page explains Java solution to problem `Maximum Average Subarray II` using `Binary Search` algorithm.

## Problem Statement

Given an array consisting of `n` integers, find the contiguous subarray whose length is greater than or equal to `k` that has the maximum average value. And you need to output the maximum average value.

Example 1:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

class MaximumAverageSubarrayIi {
public double findMaxAverage(int[] nums, int k) {
double lo = Integer.MAX_VALUE;
double hi = Integer.MIN_VALUE;

for(int i = 0; i < nums.length; i++) {
lo = Math.min(lo, nums[i]);
hi = Math.max(hi, nums[i]);
}

double avg = 0;
while(hi - lo > 1e-5) {
avg = lo + (hi - lo) / 2;
if(isLargerAvgPossible(nums, k, avg)) lo = avg;
else hi = avg;
}
return lo;
}

private boolean isLargerAvgPossible(int[] arr, int k, double avg) {
double[] remaining = new double[arr.length];
for(int i = 0; i < arr.length; i++) {
remaining[i] = arr[i] - avg;
}

//After removing avg, check if rightSum can be > 0
double rightSum = 0;
double leftSum = 0;
for(int i = 0; i < k; i++) rightSum += remaining[i];
if(rightSum >= 0) return true;

for(int i = k; i < arr.length; i++) {
rightSum += remaining[i];
leftSum += remaining[i - k];
if(leftSum < 0) {
rightSum -= leftSum;
leftSum = 0;
}
if(rightSum >= 0) return true;
}
return false;
}
}
``````

## Time Complexity

O(N log (MAX_VALUE - MIN_VALUE)) Where
N is total number of elements in an input array
MAX_VALUE is max value from input array
MIN_VALUE is min value from input array

## Space Complexity

O(N) Where
N is total number of elements in an input array