0 - Kadane's Algorithm

Kadane's Algorithm

Kadane's algorithm is a greedy/dynamic programming algorithm that can be used on an array. It is used to calculate the maximum sum subarray ending at a particular position and typically runs in $O(n)$ time.

Motivation

Q: Find a non-empty subarray with the largest sum.

We need to find a group of contiguous elements in an array that result in the maximal sum.

The brute force way to approach this would be to go through every single subarray and calculate the sum, while keeping track of the maximum sum.

For every iteration of our outer for loop, our inner loop does linear work. This makes the complexity $O(n^2)$ .

def bruteForce(nums):
    maxSum = nums[0]

    for i in range(len(nums)):
        curSum = 0
        for j in range(i, len(nums)):
            curSum += nums[j]
            maxSum = max(maxSum, curSum)
    return maxSum

public static int bruteForce(int[] nums) {
    int maxSum = nums[0];

    for (int i = 0; i < nums.length; i++) { 
        int curSum = 0;
        for (int j = i; j < nums.length; j++) {
            curSum += nums[j];
            maxSum = Math.max(maxSum, curSum);
        }    
    }       
    return maxSum;
}

int bruteForce(vector<int>& nums) {
    int maxSum = nums[0];

    for (int i = 0; i < nums.size(); i++) {
        int curSum = 0;
        for (int j = i; j < nums.size(); j++) {
            curSum += nums[j];
            maxSum = max(maxSum, curSum);
        }
    }
    return maxSum;
}

public static int BruteForce(int[] nums) {
    int maxSum = nums[0];

    for (int i = 0; i < nums.Length; i++) {
        int curSum = 0;
        for (int j = i; j < nums.Length; j++) {
            curSum += nums[j];
            maxSum = Math.Max(maxSum, curSum);
        }
    }
    return maxSum;
}

func bruteForce(nums []int) int {
    maxSum := nums[0]

    for i := 0; i < len(nums); i++ {
        curSum := 0
        for j := i; j < len(nums); j++ {
            curSum += nums[j]
            if curSum > maxSum {
                maxSum = curSum
            }
        }
    }
    return maxSum
}

fun bruteForce(nums: IntArray): Int {
    var maxSum = nums[0]

    for (i in nums.indices) {
        var curSum = 0
        for (j in i until nums.size) {
            curSum += nums[j]
            maxSum = max(maxSum, curSum)
        }
    }
    return maxSum
}

func bruteForce(_ nums: [Int]) -> Int {
  var maxSum = nums[0]

  for i in 0..<nums.count {
    var curSum = 0
    for j in i..<nums.count {
      curSum += nums[j]
      maxSum = max(maxSum, curSum)
    }
  }
  return maxSum
}

While this approach works, it is not the most efficient. The intuition behind Kadane's algorithm is that:

If all elements in the array are positive, the maximum sum subarray is the entire array.
If we ever have a negative sum subarray, that's the case we want to avoid.

Optimizing with Kadane's Algorithm

Kadane's algorithm tells us that there is a way to calculate the largest sum by only making one pass on the array, bringing the complexity down to linear time. Let's look at how that can be done.

Since we are looking for the largest sum, it is a good idea to avoid negative numbers because we know that contradicts what the question is asking for. Negative numbers will only make our sum smaller.

But sometimes we may need to include a negative number to get the surrounding positive numbers.

For example, the array [6, -2, 7] has a maximum sum of 11. If we exclude the -2, we can't include both 6 and 7.
But that's not always the case. If we have [1, -3, 7], the maximum sum is 7. Including the -3 isn't worth it just to get the 1.

The pattern is that if we ever have a negative subarray sum, we should discard it and start a new subarray. This is because we know that the sum will only get smaller if we include it.

Kadane's algorithm runs one loop.
We keep track of the curSum by adding the current element to it.
Before we add the current element, we check if the curSum is negative. If it is, we reset it to zero.
We initialize the maxSum to the first element in the array. This is technically a subarray of size 1. (We could have initialized it to any other element in the array.)
We update the maxSum by taking the maximum of the current sum and the maximum sum so far.

It's possible that every element in the array is negative. In that case, the maximum sum would be the largest negative number.

def kadanes(nums):
    maxSum = nums[0]
    curSum = 0

    for n in nums:
        curSum = max(curSum, 0)
        curSum += n
        maxSum = max(maxSum, curSum)
    return maxSum

public static int kadanes(int[] nums) {
    int maxSum = nums[0];
    int curSum = 0;

    for (int n : nums) {
        curSum = Math.max(curSum, 0);
        curSum += n;
        maxSum = Math.max(maxSum, curSum);
    }
    return maxSum;
}

int kadanes(vector<int>& nums) {
    int maxSum = nums[0];
    int curSum = 0;

    for (int n : nums) {
        curSum = max(curSum, 0);
        curSum += n;
        maxSum = max(maxSum, curSum);
    }
    return maxSum;
}

function kadanes(nums) {
    let maxSum = nums[0];
    let curSum = 0;

    for (let n of nums) {
        curSum = Math.max(curSum, 0);
        curSum += n;
        maxSum = Math.max(maxSum, curSum);
    }
    return maxSum;
}

public static int Kadanes(int[] nums) {
    int maxSum = nums[0];
    int curSum = 0;

    foreach (int n in nums) {
        curSum = Math.Max(curSum, 0);
        curSum += n;
        maxSum = Math.Max(maxSum, curSum);
    }
    return maxSum;
}

func kadanes(nums []int) int {
    maxSum := nums[0]
    curSum := 0

    for _, n := range nums {
        if curSum < 0 {
            curSum = 0
        }
        curSum += n
        if curSum > maxSum {
            maxSum = curSum
        }
    }
    return maxSum
}

fun kadanes(nums: IntArray): Int {
    var maxSum = nums[0]
    var curSum = 0

    for (n in nums) {
        curSum = max(curSum, 0)
        curSum += n
        maxSum = max(maxSum, curSum)
    }
    return maxSum
}

Sliding Window

Sometimes, a problem may ask to return the actual subarray containing the largest sum, instead of just the sum itself. Previously, we didn't have two explicit pointers that kept track of the subarray in the previous implementation but we can actually do this by keeping track of a "window". A window in this case denotes a contiguous subarray that does not break our constraint of the sum staying positive.

To do this, we can have a left pointer, L = 0, and a right pointer, R. The left and right pointers define the boundaries of our window (inclusive).

Since we want the subarray with the maximum sum, we can also have two other pointers, maxL and maxR, which keep track of the subarray that contains the maximum sum so far. This way, we don't lose them when we move L and R.

Similar to before, if our current sum becomes negative, we can move our left pointer all the way to our right pointer. This means that our constraint was broken and we remove all elements from the left and start a new window.

def slidingWindow(nums):
    maxSum = nums[0]
    curSum = 0
    maxL, maxR = 0, 0
    L = 0

    for R in range(len(nums)):
        if curSum < 0:
            curSum = 0
            L = R

        curSum += nums[R]
        if curSum > maxSum:
            maxSum = curSum
            maxL, maxR = L, R 

    return [maxL, maxR]

vector<int> slidingWindow(vector<int> nums) {
    int maxSum = nums[0];
    int curSum = 0;
    int maxL = 0, maxR = 0;
    int L = 0;

    for (int R = 0; R < nums.size(); R++) {
        if (curSum < 0) {
            curSum = 0;
            L = R;
        }
        curSum += nums[R];
        if (curSum > maxSum) {
            maxSum = curSum;
            maxL = L; 
            maxR = R;     
        }    
    }    
    return vector<int>{maxL, maxR};
}

public static int[] SlidingWindow(int[] nums) {
    int maxSum = nums[0];
    int curSum = 0;
    int maxL = 0, maxR = 0;
    int L = 0;

    for (int R = 0; R < nums.Length; R++) {
        if (curSum < 0) {
            curSum = 0;
            L = R;
        }
        curSum += nums[R];
        if (curSum > maxSum) {
            maxSum = curSum;
            maxL = L;
            maxR = R;
        }
    }
    return new int[] { maxL, maxR };
}

func slidingWindow(nums []int) []int {
    maxSum := nums[0]
    curSum := 0
    maxL := 0
    maxR := 0
    L := 0

    for R := 0; R < len(nums); R++ {
        if curSum < 0 {
            curSum = 0
            L = R
        }
        curSum += nums[R]
        if curSum > maxSum {
            maxSum = curSum
            maxL = L
            maxR = R
        }
    }
    return []int{maxL, maxR}
}

fun slidingWindow(nums: IntArray): IntArray {
    var maxSum = nums[0]
    var curSum = 0
    var maxL = 0
    var maxR = 0
    var L = 0

    for (R in nums.indices) {
        if (curSum < 0) {
            curSum = 0
            L = R
        }
        curSum += nums[R]
        if (curSum > maxSum) {
            maxSum = curSum
            maxL = L
            maxR = R
        }
    }
    return intArrayOf(maxL, maxR)
}

Time & Space Complexity

Time

Since we only make one pass through the array, our time complexity is $O(n)$ .

Space

With Kadane's algorithm, we only need a few variables to keep track of the maximum sum and the current sum. This makes our space complexity $O(1)$ .

Closing Notes

Next, let's formally look at the sliding window technique. There are two variations, fixed sliding window and variable sized sliding window, both of which are useful for different kinds of problems.

Status	Star	Problem	Difficulty	Solution
		Maximum Subarray
		Maximum Sum Circular Subarray

Advanced Algorithms

Kadane's Algorithm

Sliding Window Fixed Size

Sliding Window Variable Size

Two Pointers

Prefix Sums

Fast and Slow Pointers

Trie

Union-Find

Segment Tree

Iterative DFS

Two Heaps

Subsets

Combinations

Permutations

Dijkstra's

Prim's

Kruskal's

Topological Sort

0 / 1 Knapsack

Unbounded Knapsack

LCS

Palindromes

0 - Kadane's Algorithm

Kadane's Algorithm

Motivation

Optimizing with Kadane's Algorithm

Sliding Window

Time & Space Complexity

Time

Space

Closing Notes