LintCode题解 | 高盛面试真题：子数组的最大平均值

【题目描述】

给定一个由n个整数组成的数组，找到给定长度k的连续子数组，该子数组具有最大平均值。你需要输出最大平均值。

1 <= k <= n <= 30,000.
给定数组的元素范围是[-10,000, 10,000]。

【题目样例】

样例1

输入: nums = [1,12,-5,-6,50,3] and k = 4
输出: 12.75
解释:
最大平均为(12-5-6+50)/4 = 51/4 = 12.75

样例2

输入: nums = [4,2,1,3,3] and k = 2
输出: 3.00
解释:
最大平均为(3+3)/2 = 6/2 = 3.00

【评测与题解】

→戳这里在线评测及查看题解

/**
* 本参考程序来自九章算法，由 @MIKE 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/ 

public class Solution {
    /**
     * @param nums: an array
     * @param k: an integer
     * @return: the maximum average value
     */
    public double findMaxAverage(int[] nums, int k) {
        // Write your code here
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        int max = sum;
        
        for (int i = k; i < nums.length; i++) {
            sum = sum - nums[i - k] + nums[i];
            max = Math.max(max, sum);
        }
        return (double) max / k;
    }
}