LeetCode 643.Maximum Average Subarray 最大子数组的平均值

LeetCode 643.Maximum Average Subarray 最大子数组平均值

Description:

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.

Example 1:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Example 2:

Input: [4,0,4,,3,3], k = 5
Output: 2.8
Explanation: Maximum average is (4+0+4+3+3)/5 = 14/5 = 2.8

---

分析：

之前已经做过求最大子数组和的问题，所以我们可以按照类似的思路来解决这道题。
首先求出数组的累计和，即从第一个数开始，不断计算累计的和，存入数组中，然后根据k计算连续k个的和，即通过已经计算好的累计和数组来求解。
这里遇到的主要问题是当给定的数组长度和K值相等时，要将返回结果初始化为int max_sum = sum[k - 1];

---

代码如下：

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
class Solution {
public:
	double findMaxAverage(vector<int>& nums, int k) {
		int len = nums.size();
		vector<int> sum(len);
		sum[0] = nums[0];
		//int max_sum = sum[0];
		for (int i = 1; i < len; i++) {
			sum[i] = nums[i] + sum[i - 1];
			//sum[i] = nums[i] + (sum[i - 1] > 0 ? sum[i - 1] : 0);
			//max_sum = max(max_sum, sum[i]);
		}
		//for (int i = 0; i < len; i++) {
			//cout << sum[i] << " ";
		//}
		//cout << endl;
		int max_sum = sum[k - 1];// 这里是因为当k与数组长度相等时，要初始化为sum数组最后一个数
		for (int i = 0; i < len - k; i++) {
			int temp = sum[i + k] - sum[i];
			max_sum = max(max_sum, temp);
		}
		return (double)max_sum / k;
	}
};

int main() {
	Solution s;
	int n;
	cin >> n;
	vector<int> nums(n);
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	int k;
	cin >> k;
	cout << s.findMaxAverage(nums, k) << endl;
	return 0;
}

---

运行结果如下：