MaxSubarraySum.SlidingWindow.md

Max Subarray Sum Algorithm using the Sliding Window method

Give I have an array of integers, I want to determine the largest sum of a consecutive sub set of those integers.

maxSubarraySum(arr, num)

The array passed through will only ever contain integers (Positive and Negative whole numbers including 0). The array passed through will never be empty. The number passed through will always be positive(Greater than 0). The number passed through might be longer than the array. In the case where the number is larger than the array length, return null.

Examples

maxSubarraySum([100,200,300,400], 2)       // 700
maxSubarraySum([1,4,2,10,23,3,1,0,20], 4)  // 39 
maxSubarraySum([-3,4,0,-2,6,-1], 2)        // 5
maxSubarraySum([3,-2,7,-4,1,-1,4,-2,1],2)  // 5
maxSubarraySum([2,3], 3)                   // null

Let's break it down!

There are a few ways we can achive this logic, this article will be covering the Sliding Window method.
Let's start be analyzing the task at hand with the following example.

maxSubarraySum([100,200,300,400], 2)

We have a list of integers ([100,200,300,400]) and we need to add them together (2) at a time and determine which pair has the largest sum.
To achive this we will define the starting window as the first (2) integers in the array.

[100,200,300,400]
  ^---^

window = [100, 200];
windowSum = 300;
maxSum = 300;

Next, let's move the window forward one element and determine the sum
If the sum of the window is larger than the maxSum, change maxSum to be the window sum.

[100,200,300,400]
      ^---^

window = [200, 300];
windowSum = 500;
maxSum = 500;

Finally, we move the window forward once more and determin the sum
Since the window can not move forward without breaching the array length, this is the last possible subarray we can evaluate.

[100,200,300,400]
          ^---^

window = [300, 400];
windowSum = 700;
maxSum = 700;

We now know that the max subarray sum for [100,200,300,400] is 700!

Pseudo Code

Let's start pseudo coding!
First we need to check if the length of the array is shorter than the subarray number.

+// If the num is greater than the arr length, return null

Next, we can define the window variable and loop over the array (n) times to determine the starting window value.

// If the num is greater than the arr length, return null
+// Define the window variable equal to 0
+// loop over the array num times
+  // add window's value with array[i] value

Then, we can define the maxSum as being equal to the starting window value.

// If the num is greater than the arr length, return null
// Define the window variable equal to 0
// loop over the array num times
  // add window's value with array[i] value
+// define maxSum to equal window

Finally, we want to move the window forwards and check the sum.
To do this we can add the next value to the window

[100,200,300,400]
  ^---^
currentWindow = [100, 200];
[100,200,300,400]
  ^---^---^
updateWindow = [100, 200, 300];

And subtract the first value from the window.

[100,200,300,400]
  ^---^---^
currentWindow = [100, 200, 300];
[100,200,300,400]
      ^---^
updateWindow = [200, 300];

To achive this we can loop over the array again and set j equal to num
We set j equal to num because arrays are 0 indexed and we want j to be one index ahead of the current window
So, if num is 2 that would make our first window's indexes 0 and 1 or the first and second elements in the array.
j would be index 2 or the third element in the array.

For every loop, we add the value at arr[ j ] (the next element in the array) to the window, subtract the value at arr[ j - num ] (the first element in the window) from the window, and if window is greater than maxSum, set maxSum equal to window.
After the loop we return maxSum.

// If the num is greater than the arr length, return null
// Define the window variable equal to 0
// loop over the array num times
  // add window's value with array[i] value
// define maxSum to equal window
+// loop over the array again where j is equal to num
+  // add array[j] value to window
+  // subtract array[j - num] from window
+  // If window's value is greater than maxSum, set maxSum equal to window value
return maxSum;

Let's code!

The code for this algorithm is simply two variables and two loops.
The first loop is to define the starting window and the second is the move the window forward until the end of the array.
As always, lets start with weeding out the edge case where the number provided is larger than the array.

function maxSubarraySum(arr, num){
  // If the num is greater than the arr length, return null
  if (arr.length < num) return null;
}

Next, we can define the window variable and loop over the array (n) times to determine the starting window value.

function maxSubarraySum(arr, num){
  if (arr.length < num) return null;
  // Define the window variable equal to 0
  let window = 0;
  // loop over the array num times
  for (let i = 0; i < num; i++) {
      // add window's value with array[i] value
      window += arr[i];
  }
}

Then, we can define the maxSum as being equal to the starting window value.

function maxSubarraySum(arr, num){
  if (arr.length < num) return null;
  let window = 0;
  for (let i = 0; i < num; i++) {
      window += arr[i];
  }
  // define maxSum to equal window
  let maxSum = window;
}

Finally, we want to move the window forwards and check the sum.

function maxSubarraySum(arr, num){
  if (arr.length < num) return null;
  let window = 0;
  for (let i = 0; i < num; i++) {
      window += arr[i];
  }
  let maxSum = window;
  // loop over the array again where j is equal to num
  for (let j = num; j < arr.length; j++) {
    // add array[j] value to window
    // subtract array[j - num] from window
    window += arr[j] - arr[j - num];
    // If window's value is greater than maxSum, set maxSum equal to window value
    maxSum = Math.max(window, maxSum);
  }
  return maxSum;
}

Tada! We have an algorithm that produces the max sub from a subarray!

Time Complexity - O(N)

Space Complexity - O(1)

function maxSubarraySum(arr, num){
  if (arr.length < num) return null;
  let window = 0;
  for (let i = 0; i < num; i++) {
      window += arr[i];
  }
  let maxSum = window;
  for (let j = num; j < arr.length; j++) {
    window += arr[j] - arr[j - num];
    maxSum = Math.max(window, maxSum);
  }
  return maxSum;
}