Solution: Maximum Sum Subarray of Size K

Problem Statement

Given an array of positive numbers and a positive number 'k,' find the maximum sum of any contiguous subarray of size 'k'.

Example 1:

Input: arr = [2, 1, 5, 1, 3, 2], k=3 
Output: 9
Explanation: Subarray with maximum sum is [5, 1, 3].

Example 2:

Input: arr = [2, 3, 4, 1, 5], k=2 
Output: 7
Explanation: Subarray with maximum sum is [3, 4].

Solution

To solve this problem, we will use a brute force approach. The brute force method involves examining every possible subarray of size k and calculating their sums

.....

Like the course? Get enrolled and start learning!

Federico Madden

· a year ago

My solution using pythonic contructs like aggregation functions and array slicing. Here we assume slicing uses no extra space, though it may in practice

class Solution:
  def findMaxSumSubArray(self,k, arr):
    # return 0 if k=0
    if k == 0:
      return 0
    if k == 1:
      return max(arr)
    # init max sum to 0
    max_sum = 0
    # first iteration
    # init current sum to sum(arr[0:k]) (python array slicing is end-exclusive)
    curr_sum = sum(arr[0:k])
    # update max sum
    max_sum = max(curr_sum, max_sum)
    # loop where we iterate over start (0) and end (k) elts, both increment by 1 after each iteration
    # We need to gracefully handle the case where k=n
    for start, end in zip(arr, arr[k:]):
      # update the current sum by subtracting the start elt