Maximum Average Subarray

Given an array with positive and negative numbers, find the maximum average subarray which length should be greater or equal to given length k.

Example

Given nums = [1, 12, -5, -6, 50, 3], k = 3

Return 15.667 // (-6 + 50 + 3) / 3 = 15.667

利用队列建立窗口

 1 public class Solution {
 2     /**
 3      * @param nums an array with positive and negative numbers
 4      * @param k an integer
 5      * @return the maximum average
 6      */
 7     public double maxAverage(int[] nums, int k) {
 8         // Write your code here
 9         if(k<=0||nums==null||nums.length==0) return 0;
10         double average = Double.NEGATIVE_INFINITY;
11         double sum = 0;
12         Queue<Integer> queue = new LinkedList<Integer>();
13         
14         for(int i=0;i< nums.length;i++){
15             if(i>=k){
16                 int out = queue.poll();
17                 sum-=out;
18             }
19             queue.offer(nums[i]);
20             sum+=nums[i];
21             if(i>=k-1){
22                 average = Math.max(average, sum/k);
23             }
24         }
25         
26         return average;
27     }
28 }