Understanding Kadane’s Algorithm for Maximum Subarray

If you want to Master Maximum Subarray Sum Problem, you are in the right place!

Kadane’s Algorithm is a popular and efficient algorithm used to find the maximum sum of a subarray within a given array of integers. It is a dynamic programming technique that solves the maximum subarray sum problem in linear time complexity, O(n), where ’n’ is the size of the array.

The algorithm works by iterating over an array while keeping track of two variables:

currentSum and maxSumSoFar These variables are being used in this algorithm so that we solve the maximum subarray problem using O(n) time complexity.

• currentSum: It keeps track of the maximum sum of a subarray ending at the current Index.
• maxSumSoFar: It represents the maximum sum encountered so far during the iteration

# Setting Variables

Initialize currentSum to 0 and maxSumSoFar to MIN_INT (minimum integer possible)

We need to follow these 2 simple steps on every iteration of the array:

# Steps:

Set currentSum = currentSum + a[i] and check if

• currentSum > maxSumSoFar then maxSumSoFar = currentSum
• currentSum < 0 then currentSum = 0

Once the loop is finished, the maxSumSoFar is the Maximum sum of the subarray.

Here is a full example of how to implement Kadane’s Algorithm.

class Kadane {
  arr: number[]
  crrSum: number
  maxSumSoFar: number

  constructor(arr: number[]) {
    this.arr = arr
    this.crrSum = 0
    this.maxSumSoFar = Math.pow(-2, 53)
  }
  
  findMax(left: number = 0, right: number = this.arr.length - 1) {
    for(let i = left; i <= right; i++) {
      const crrElement = this.arr[i]
      this.crrSum += crrElement
      if (this.crrSum > this.maxSumSoFar) {
         this.maxSumSoFar = this.crrSum
      }
      if (this.crrSum < 0) {
         this.crrSum = 0
      }
    }
    return this.maxSumSoFar
  }
}

const arr1 = [-1, 2, 3, 5, -10, 20, 3, 50, -100]
const kadane = new Kadane(arr)

console.log('Max Sum in Array', kadane.findMax()) // 73

const arr2 = [ -2, -3, 4, -1, -2, 1, 5, -3 ]
const kadane2 = new Kadane(arr)

console.log('Max Sum in Sub Array', kadane.findMax(3, 6)) // 6

The above example finds the maximum subarray sum in O(n) Time complexity.

I hope now you have some basic knowledge of how Kadane’s algorithm works.