Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/643.html
643. Maximum Average Subarray I (Easy)
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
Note:
- 1 <=
k
<=n
<= 30,000. - Elements of the given array will be in the range [-10,000, 10,000].
Companies:
Amazon
Related Topics:
Array
Similar Questions:
Solution 1.
// OJ: https://leetcode.com/problems/maximum-average-subarray-i/
// Time: O(N)
// Space: O(1)
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int sum = 0, maxSum = INT_MIN;
for (int i = 0; i < nums.size(); ++i) {
if (i < k) {
sum += nums[i];
if (i == k - 1) maxSum = sum;
} else {
sum += nums[i] - nums[i - k];
maxSum = max(maxSum, sum);
}
}
return (double)maxSum / k;
}
};
-
class Solution { public double findMaxAverage(int[] nums, int k) { int length = nums.length; int sum = 0; for (int i = 0; i < k; i++) sum += nums[i]; int maxSum = sum; for (int i = k; i < length; i++) { sum -= nums[i - k]; sum += nums[i]; maxSum = Math.max(maxSum, sum); } return 1.0 * maxSum / k; } } ############ class Solution { public double findMaxAverage(int[] nums, int k) { int s = 0; for (int i = 0; i < k; ++i) { s += nums[i]; } int ans = s; for (int i = k; i < nums.length; ++i) { s += (nums[i] - nums[i - k]); ans = Math.max(ans, s); } return ans * 1.0 / k; } }
-
// OJ: https://leetcode.com/problems/maximum-average-subarray-i/ // Time: O(N) // Space: O(1) class Solution { public: double findMaxAverage(vector<int>& nums, int k) { int sum = 0, maxSum = INT_MIN; for (int i = 0; i < nums.size(); ++i) { if (i < k) { sum += nums[i]; if (i == k - 1) maxSum = sum; } else { sum += nums[i] - nums[i - k]; maxSum = max(maxSum, sum); } } return (double)maxSum / k; } };
-
class Solution: def findMaxAverage(self, nums: List[int], k: int) -> float: s = sum(nums[:k]) ans = s for i in range(k, len(nums)): s += nums[i] - nums[i - k] ans = max(ans, s) return ans / k ############ from collections import deque class Solution(object): def findMaxAverage(self, nums, k): """ :type nums: List[int] :type k: int :rtype: float """ s = 0 ans = float("-inf") queue = deque([]) for num in nums: queue.append(num) s += num if len(queue) > k: s -= queue.popleft() if len(queue) == k: ans = max(ans, float(s) / k) return ans
-
function findMaxAverage(nums: number[], k: number): number { let n = nums.length; let ans = 0; let sum = 0; // 前k for (let i = 0; i < k; i++) { sum += nums[i]; } ans = sum; for (let i = k; i < n; i++) { sum += nums[i] - nums[i - k]; ans = Math.max(ans, sum); } return ans / k; }
-
impl Solution { pub fn find_max_average(nums: Vec<i32>, k: i32) -> f64 { let k = k as usize; let n = nums.len(); let mut sum = nums.iter().take(k).sum::<i32>(); let mut max = sum; for i in k..n { sum += nums[i] - nums[i - k]; max = max.max(sum); } f64::from(max) / f64::from(k as i32) } }