Home/

...

/

Maximum Sum Subarray of Size K (easy)

Maximum Sum Subarray of Size K (easy)

Resources for finding the maximum sum among all subarrays

Real-world problems

A variant of the “maximum sum subarray of size K” problem comes up when designing a feature for the computer player in the card game Fizzle.

The winning strategy in a card game

In Fizzle, the dealer shuffles the deck and spreads out all the cards facing upwards in a linear fashion. Then, players take turns rolling a die. Suppose the number rolled is kk. Players will then take turns to remove kk cards from the deck, while respecting this constraint: they may only pick cards from either the deck’s right or left side.

Each player’s goal is to pick out the cards with maximum points. Each numbered card carries points corresponding to its number, and the faced cards, jack, queen, king, and ace, carry 1111, 1212, 1313, and 1414 points, respectively.

Our task is to create a feature for Fizzle’s computer player. We will be given the deck’s current state and the number the player rolled. We need to determine the maximum score that the player can obtain on that turn.

Let’s take a look at the following example:

In the example above, the player picked the cards 66, 33, 55, and 33 in the given order, to obtain the maximum points possible, that is 1717.

We will receive this deck of cards in the form of an array, such as {5, 3, 4, 8, 2, 3, 2, 6, 3}. The number obtained from rolling the die will be given as an integer, such as 4.

Our function needs to return the maximum number of points obtained.

Encourage the students to see the link between this problem and the sliding window pattern. Can they see a window, that is, a contiguous set of cards (or numbers representing cards) in this problem?

Some questions to think about:

  • What is the size of the window?
  • Are we interested in the cards inside the window or outside?
  • Is it an individual property we are interested in or an aggregate one?
  • Is it a simple linear array, or a circular array?

Dry-run templates

This is the implementation of the more efficient solution provided for the problem posed in the lesson:

Press + to interact
Python
def max_sub_array_of_size_k(k, arr):
  max_sum , window_sum = 0, 0
  window_start = 0
  for window_end in range(len(arr)):
    window_sum += arr[window_end]  # add the next element
    # slide the window, we don't need to slide if we've not hit the required window size of 'k'
    if window_end >= k-1:
      max_sum = max(max_sum, window_sum)
      window_sum -= arr[window_start]  # subtract the element going out
      window_start += 1  # slide the window ahead
  return max_sum
def main():
  print("Maximum sum of a subarray of size K: " + str(max_sub_array_of_size_k(3, [2, 1, 5, 1, 3, 2])))
  print("Maximum sum of a subarray of size K: " + str(max_sub_array_of_size_k(2, [2, 3, 4, 1, 5])))
main()

Students may be encouraged to run through the provided solution with the following sample inputs:

Sample Input #1

K = 3, Array: {2, 1, 5, 3, 2}

Iteration number

Line number

windowStart

windowEnd

windowSum

maxSum

-

2 - 3

0

-

0

0

1

5 - 6

0

0

2

0

2

5 - 6

0

1

3

0

3

5 - 6

0

2

8

0

3

8 - 11

1

2

6

8

4

5 - 6

1

3

7

8

4

8 - 11

2

3

6

8

5

5 - 6

2

4

9

8

5

8 - 11

3

4

4

9

6

5 - 6

3

5

6

9

6

8 - 11

4

5

5

9

Sample Input #2

K = 2, Array: {2, 3, 4, 1, 5}

Iteration number

Line number

windowStart

windowEnd

windowSum

maxSum

-

2 - 3

0

-

0

0

1

5 - 6

0

0

2

0

2

5 - 6

0

1

5

0

2

8 - 11

1

1

3

5

3

5 - 6

1

2

7

5

3

8 - 11

2

2

4

7

4

5 - 6

2

3

5

7

4

8 - 11

3

3

1

7

5

5 - 6

3

4

6

7

5

8 - 11

4

4

5

7

Step-by-step solution construction

We have already learned how to slide a window of a size of our choice across an array of values, as well as how to calculate aggregate values such as the sum and average of the current window.

Run the code below to verify that the correct window is identified and that the sum calculated for each window is correct:

Press + to interact
Python
# -*- coding: utf-8 -*-
def max_sub_array_of_size_k(k, arr):
  window_sum = 0
  window_start = 0
  for window_end in range(len(arr)):
    print("\nLoop index: " + str(window_end))
    window_sum += arr[window_end]  # add the next element
    # slide the window, we don't need to slide if we've not hit the required window size of 'k'
    if window_end >= k-1:
      print("Window starts at index " + str(window_start) + ": " + 
        print_array_with_slice_markers(arr, window_start, window_end, '«', '»'))
      print("Sum of current window: " + str(window_sum))
      window_sum -= arr[window_start]  # subtract the element going out
      window_start += 1  # slide the window ahead
  return 0
def print_array_with_slice_markers(arr, slice_start, slice_end, slice_opening, slice_ending):
  out = "[";
  for i in range(len(arr)):
    if slice_start == i:
      out += slice_opening
    out +=  str(arr[i]) + (slice_ending if slice_end == i else "") + ", ";
  out = out[:-2];
  out += "]";
  return out
def main():
  window_sizes = [3, 2];
  input_arrays = [[2, 1, 5, 1, 3, 2], [2, 3, 4, 1, 5]];
  for i in range(len(window_sizes)):
    print("Window size: " + str(window_sizes[i]) + ", input array: " + str(input_arrays[i]))
    print("Maximum sum of a subarray of size K = " + str(window_sizes[i]) + ": " + str(max_sub_array_of_size_k(window_sizes[i], input_arrays[i])))
    print("-------------------------------------------------------------------------------------------------------\n")
main()

Now, all we need to do is to check if each newly calculated sum is greater than the largest sum already encountered. If it is, it becomes the new maximum sum.

Let’s use a new variable, max_sum, to store the maximum sum calculated so far and add the logic (see lines 4 and 13) to update its value:

Press + to interact
Python
# -*- coding: utf-8 -*-
def max_sub_array_of_size_k(k, arr):
  max_sum , window_sum = 0, 0
  window_start = 0
  star = ''
  for window_end in range(len(arr)):
    print("\nLoop index: " + str(window_end))
    window_sum += arr[window_end]  # add the next element
    # slide the window, we don't need to slide if we've not hit the required window size of 'k'
    if window_end >= k-1:
      star = '*' if max_sum < window_sum else ''
      max_sum = max(max_sum, window_sum)
      print("Window starts at index " + str(window_start) + ": " + 
        print_array_with_slice_markers(arr, window_start, window_end, '«', '»'))
      print("Sum of current window: " + str(window_sum) + star)
      window_sum -= arr[window_start]  # subtract the element going out
      window_start += 1  # slide the window ahead
  return max_sum
def print_array_with_slice_markers(arr, slice_start, slice_end, slice_opening, slice_ending):
  out = "[";
  for i in range(len(arr)):
    if slice_start == i:
      out += slice_opening
    out +=  str(arr[i]) + (slice_ending if slice_end == i else "") + ", ";
  out = out[:-2];
  out += "]";
  return out
def main():
  window_sizes = [3, 2];
  input_arrays = [[2, 1, 5, 1, 3, 2], [2, 3, 4, 1, 5]];
  for i in range(len(window_sizes)):
    print("Window size: " + str(window_sizes[i]) + ", input array: " + str(input_arrays[i]))
    print("Maximum sum of a subarray of size K = " + str(window_sizes[i]) + ": " + str(max_sub_array_of_size_k(window_sizes[i], input_arrays[i])))
    print("-------------------------------------------------------------------------------------------------------\n")
main()

The code on lines 6 and 12 does not affect program execution. It simply allows us to detect when a new maximum sum has been identified, so that we may indicate this in the output statement on line 17.

How may we modify this code to develop the feature for the computer player for Fizzle?