Max Sum Subarray Of Size K
Description
Given an array of integers and a number k, find the maximum sum of a contiguous subarray of size k.
Example 1:
Input: nums = [2, 1, 5, 1, 3, 2], k = 3
Output: 9
Explanation: Subarray with maximum sum is [5, 1, 3] with sum = 9.
Example 2:
Input: nums = [2, 3, 4, 1, 5], k = 2
Output: 7
Explanation: Subarray with maximum sum is [3, 4] with sum = 7.
Example 3:
Input: nums = [-1, -2, -3, -4], k = 2
Output: -3
Explanation: Subarray with maximum sum is [-1, -2] with sum = -3. Even with all negatives, we must pick k elements.
Constraints
1 <= k <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
Complexity
Show Complexity
- Time:
O(n) - Space:
O(1)
Hints
Show Hints
- Pattern
- Use a fixed-size sliding window of size k
- Approach
- First compute sum of first k elements. Then slide: add nums[i], subtract nums[i-k], track max.
- Complexity
- Maintain window sum - add new element, subtract old element
Solutions
Show PY Solution
def solution(nums, k):
sm = 0
for i in range(k):
sm += nums[i]
result = sm
for i in range(k, len(nums)):
sm += nums[i]
sm -= nums[i - k]
result = max(result, sm)
return result
# length = len(nums)
#
# if k == 0:
# return 0
#
# ans = 0
# i = 0
# curr = 0
# while i < k:
# curr += nums[i]
# i += 1
#
# ans = curr
#
# while i < length:
# curr += nums[i] - nums[i - k]
# ans = max(ans, curr)
# i += 1
#
# return ans