LeetCode //C - 643. Maximum Average Subarray I

2023-12-24 22:54:04

643. Maximum Average Subarray I

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 1 0 ? 5 10^{-5} 10?5 will be accepted.
?

Example 1:

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

Example 2:

Input: nums = [5], k = 1
Output: 5.00000

Constraints:
  • n == nums.length
  • 1 < = k < = n < = 1 0 5 1 <= k <= n <= 10^5 1<=k<=n<=105
  • ? 1 0 4 < = n u m s [ i ] < = 1 0 4 -10^4 <= nums[i] <= 10^4 ?104<=nums[i]<=104

From: LeetCode
Link: 643. Maximum Average Subarray I


Solution:

Ideas:

The function starts by calculating the sum of the first k elements. Then, it slides the window across the array, updating the sum for each new window by subtracting the element that is left behind and adding the new element. It keeps track of the maximum sum encountered. Finally, it returns the maximum average by dividing the maximum sum by k.

Code:
double findMaxAverage(int* nums, int numsSize, int k) {
    // Initial calculation for the first window
    double sum = 0;
    for (int i = 0; i < k; i++) {
        sum += nums[i];
    }

    double maxSum = sum;

    // Slide the window, update the sum and maxSum
    for (int i = k; i < numsSize; i++) {
        sum = sum - nums[i - k] + nums[i];
        if (sum > maxSum) {
            maxSum = sum;
        }
    }

    // Return the maximum average
    return maxSum / k;
}

文章来源:https://blog.csdn.net/navicheung/article/details/135187372
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。