nathanwailes

Sliding Window

Mar 26th, 2024 (edited)
671
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.03 KB | None | 0 0
  1. """
  2. Pseudocode:
  3.  
  4. # sliding window - need the full object to slide over and the size of the window
  5.    # handle the edge case where the window is bigger than the array
  6.    # calculate the initial window and set the best-found-value to it
  7.     # create a pointer to the start of the window
  8.    # loop through valid values for the end of the window
  9.        # calculate window value
  10.        # update best answer found so far
  11.        # increment start of window
  12.    # return the best answer you found
  13.  
  14. Mistakes I've made:
  15. - I forgot to increment the 'start' index variable.
  16. - I initialized l to k-1 instead of 0. I guess I got it confused with the r pointer.
  17. """
  18.  
  19. def max_subarray(arr, k):
  20.     if k > len(arr):
  21.         return -1
  22.     max_sum = window_sum = sum(arr[:k])
  23.     l = 0
  24.     for r in range(k, len(arr)):
  25.         window_sum = window_sum - arr[l] + arr[r]
  26.         max_sum = max(window_sum, max_sum)
  27.         l += 1
  28.     return max_sum
  29.  
  30. arr = [2, 3, 4, 1, 5]
  31. print(max_subarray(arr, 3))  # Output: 10, which is the sum of [4, 1, 5]
Advertisement
Add Comment
Please, Sign In to add comment