Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

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!
P

Perry Robinson

· 4 years ago

I am comparing this problem to what I see on leetcode for 643. Maximum Average Subarray I. When you have to account for negative numbers, this solution in the course does not work. How do we modify our solution to make it work with negative numbers?

Show 6 replies
U

usha_sahu2000

· 2 years ago

class Solution:
  def findMaxSumSubArray(self,k, arr):
    # TODO: Write your code here
    maxsum=[]
    
    for i in range(0,len(arr)-k+1):
      maxsum=max(maxsum,arr[i:i+k],key=sum)

    return sum(maxsum)
Luis Roel

Luis Roel

· 3 years ago

class Solution:
  def findMaxSumSubArray(self,k, arr):
    # Check if arra is empty
    if not arr:
      return -1

    # Pointer to leftmost index of our window
    l = 0
    # Set max_so_far to the sum 
    max_so_far = sum(arr[:k])
    curr_sum = max_so_far

    # Start iterating from size k onwards
    for r in range(k, len(arr)):
      # Add element from right into current sum
      curr_sum += arr[r]

      # Now check if our window exceeds size k
      if (r - l) + 1 > k:
        # Subtrack leftmost element of window
        curr_sum -= arr[l]
        # Shift left
        l += 1
      
      # In either case, update max
      max_so_far = max(max_so_far, curr_sum)
    
    return max_so_far
Show 1 reply
Boris K

Boris K

· 2 years ago

class Solution:
  def findMaxSumSubArray(self,k, arr):
    maxSum = 0
    l = 0
    for i in range(l,len(arr)):
      curSum = sum(arr[l:l+k])
      maxSum = max(maxSum, curSum)
      l += 1
    return maxSum
Tu Huy Nguyen

Tu Huy Nguyen

· a year ago

In sliding window solution, shouldn't if window_end >= k - 1: be if window_end - window_start > k - 1: for better? window_end - window_start represents the size of the windows.

Show 1 reply
Federico Madden

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
Sandy Straw

Sandy Straw

· 4 months ago

Imo the solution here doesnt capture the essence of what sliding window problems should operate like. Avoid using a for loop, instead use a while loop and another condition inside that checks the length j - i + 1 > k and on that basis moves the window. I'm just talking abt semantic preferences though, no worries