Finding max sum of subarray with a given length in an array

0 / 390
subarray sum

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: [2, 1, 5, 1, 3, 2], k=3  Output: 9 Explanation: Subarray with maximum sum is [5, 1, 3].    

Example 2:

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

 

Solution

A basic brute force solution will be to calculate the sum of all ‘k’ sized subarrays of the given array, to find the subarray with the highest sum. We can start from every index of the given array and add the next ‘k’ elements to find the sum of the subarray. Following is the visual representation of this algorithm for Example-1:  
subarray sum

subarray sum depiction

    Javascript Code below (brute force approach):-     
<script>
function max_sub_array_of_size_k(k, arr) {
  let maxSum = 0,
    windowSum = 0;
  // loop through start till array length - k
  for (i = 0; i < arr.length - k + 1; i++) {
    windowSum = 0;
    // loop through i to i + k elements
    for (j = i; j < i + k; j++) {
      windowSum += arr[j];
    }
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}


document.write(`Maximum sum of a subarray of size K: ${max_sub_array_of_size_k(3, [2, 1, 5, 1, 3, 2])}<br/>`);
document.write(`Maximum sum of a subarray of size K: ${max_sub_array_of_size_k(2, [2, 3, 4, 1, 5])}<br/>`);
</script>
    The time complexity of the above algorithm will be O(N*K), where ‘N’ is the total number of elements in the given array and K is the size of sub-array. The above solution works but isn’t efficient for large data sets. It will fail and run out of time. We need a better solution. To solve such problems, we use a pattern called “sliding window pattern or mechanism”    

Sliding window mechanism

 

If we observe closely, we realize that we can reuse the sum of previous sub-array at each point to calculate the sum of current sub-array a.k.a window. We consider each sub-array as a Sliding Window of size ‘k’. To calculate the sum of the next sub-array, we need to slide the window ahead by one element. So to slide the window forward and calculate the sum of the new position of the sliding window, we need to do two things:

  1. Subtract the element going out of the sliding window i.e., subtract the first element of the window.
  2. Add the new element getting included in the sliding window i.e., the element coming right after the end of the window.
 

This approach will save us from re-calculating the sum of the overlapping part of the sliding window. Here is what our algorithm will look like:

  
<script>
function max_sub_array_of_size_k(k, arr) {
	var maxSum = 0;
	var windowStart = 0;

	var windowSum = 0;


	for (var windowEnd = 0; windowEnd < arr.length; windowEnd++) {
		windowSum += arr[windowEnd];

		if (windowEnd >= k - 1) {
			maxSum = Math.max(maxSum, windowSum);
			windowSum -= arr[windowStart];
			windowStart++;
		}
	}

	return maxSum;
}


document.write(`Maximum sum of a subarray of size K: ${max_sub_array_of_size_k(3, [2, 1, 5, 1, 3, 2])}<br/>`);
document.write(`Maximum sum of a subarray of size K: ${max_sub_array_of_size_k(2, [2, 3, 4, 1, 5])}<br/>`);
</script>

 

Time Complexity 

The time complexity of the above algorithm will be O(N).

 

Space Complexity 

The algorithm runs in constant space O(1).

   

Comments

comments


Tags :

Related Posts