Problem

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

Examples

Example 1

1
2
3

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

Example 2

1
2
3

Input: nums[] = {4, 2, 3, 5, 1, 2}, k = 3
Output: 10
Explanation: Subarray with maximum sum is [2, 3, 5]

Solution

Method 1 - Brute Force

The brute approach is to iterate through the array and calculate sum of all subarrays of size k using nested loops, and return the length of the maximum sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {

	public int maxSumSubarrayOfSizeK(int[] nums, int k) {
		int ans = 0, subarraySum;

		for (int i = 0; i <= nums.length - k; i++) {
			subarraySum = 0;

			for (int j = i; j < i + k; j++) {
				subarraySum += nums[j];
			}

			ans = Math.max(ans, subarraySum);
		}

		return ans;
	}
}

Complexity

  • ⏰ Time complexity: O(n*k)
  • 🧺 Space complexity: O(1)

Method 2 - Sliding Window

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {

	public int maxSumSubarrayOfSizeK(int[] nums, int k) {
		if (k == 0 || nums.length == 0) {
			return 0;
		}

		int ans = Integer.MIN_VALUE;
		int left = 0;
		int windowSum = 0;

		for (int right = 0; right < nums.length; right++) {
			windowSum += nums[right]; 
			if (right - left + 1 == k) { 
				ans = Math.max(ans, windowSum);
				windowSum -= nums[left]; 
				left++; 
			}
		}

		return ans;
	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)