Leetcode Problem 644. Maximum Average Subarray II

644. Maximum Average Subarray II

Leetcode Solutions

Binary Search for Maximum Average Subarray

  1. Initialize left as the minimum value in nums and right as the maximum value in nums.
  2. While right - left is greater than 10^-5, do the following: a. Calculate mid as (left + right) / 2. b. Initialize sum and prev to 0, and min_sum to 0. c. Iterate through the array, updating sum by adding nums[i] - mid. d. If i is greater than or equal to k, update min_sum to the minimum of min_sum and prev, and update prev by adding nums[i - k] - mid. e. If sum is greater than or equal to min_sum, set left to mid. Otherwise, set right to mid.
  3. Return left as the maximum average subarray value.
UML Thumbnail

Cumulative Sum with Sliding Window

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...