This algorithm finds the largest contiguous subarray within a one-dimensional array of numbers that has the largest sum. This can be used in questions where you have to return the maximum subarray.

Big O

This algorithm solves the problem in O(n) time with O(1)space.

Explanation

There are three values that we need to gather as we work through the array.

• CurrentValue - the current value of the element in the array.

• CurrentMax - the current total of contiguous elements.

• GlobalMax - the largest currentMax total we have so far seen.

To start with we will create a function that holds our given array -

function kadanesAlgorithm(arr) {}

To create this in code we will need to create currentMax and GlobalMax variables. To work through each element of the array we will use a for loop.

function kadanesAlgorithm(arr) {
  let currentMax = arr[0];
  let globalMax = arr[0];

  for(let i = 1; i < arr.length; i ++) {}
}

Then we need to check if the sum of the current value + the sum of the previous subarray are greater than the current value.

function kadanesAlgorithm(arr) {
let maxCurrent = arr[0];
let maxGlobal = arr[0];
  for(let i = 1; i < arr.length; i ++) {
    maxCurrent = Math.max(arr[i], maxCurrent + arr[i])
  }
}

Then we compare the current Max to the GlobalMax and set Global Max to equal currentMax if it is larger.

function kadanesAlgorithm(arr) {
let maxCurrent = arr[0];
let maxGlobal = arr[0];
  for(let i = 1; i < arr.length; i ++) {
    maxCurrent = Math.max(arr[i], maxCurrent + arr[i])
    if (maxCurrent > maxGlobal ){
      maxGlobal = maxCurrent;
    }
  }
}

The final step is to return GlobalMax. Here we have our final code.

function kadanesAlgorithm(arr) {
let maxCurrent = arr[0];
let maxGlobal = arr[0];
  for(let i = 1; i < arr.length; i ++) {
    maxCurrent = Math.max(arr[i], maxCurrent + arr[i])
    if (maxCurrent > maxGlobal ){
      maxGlobal = maxCurrent;
    }
  }
  return MaxGlobal
}