Applications Of Kadane’s Algorithm

We all might have heard about Kadane’s algorithm in our higher studies or while preparing for coding interviews. Have you ever wonder where this simple yet efficient algorithm finds place in this tech world? I had that question, so I did some research on it, and found some interesting things to grind on…

Briefing on Kadane’s Algorithm

Kadane’s algorithm is originally designed for 1D array. But do you know it is applicable for 2D arrays also? This pays the way for its real world application.

Algorithm for 1D Array

long maxSubarraySum(int arr[], int n){
        Long max_so_far = Long.MIN_VALUE;
        Long max_value_ending = 0L;
        
        for(int val : arr) {
            max_value_ending += val;
            max_so_far = Math.max(max_so_far, max_value_ending);
            if(max_value_ending < 0) {
                max_value_ending = 0L;
            }
        }
        
        return max_so_far;
}

The above code returns the max subarray value for a 1D array. There are tons of articles out there which explains Kadane’s algorithm. So let’s restrict ourself to its application and 2D algorithm which we won’t find too ofter in our regular encounters.

Algorithm for 2D Matrix

Let me explain this algo in simpler terms

What we’re going to find?
A rectangle with maximum sum, so we need starting row, ending row, starting column and ending column.

How we’re going to get that?
1. Fix a left column.
2. Iterate over each column to the right of left column ,sum the value and store it an 1D array.
3. Apply kadane’s 1D algorithm and find the max subarray in that 1D array for each right column movement.
4. Now in each iteration compare the max so far with the result obtained.
5. If greater, replace the max so far and update the start column, end column, start row and end row.

Illustrations
Lets assume maxSoFar = 0, leftColumn = 0, rightColumn = 0, topColumn = 0, bottomColumn = 0.
I will try to give some illustration for first iteration

keeping 0th column constant

move right column one by one. Let’s denote right column by blue boundary.

right column at initial position which is same as left column

now the temp row will be same as left column as there is no column before that.

temp row

now on applying kadanae 1D algo on this temp row
maxSum = 3, start = 2, end = 2
maxSoFar = 3, top = 2, end = 2, left = 0, right = 0

Now moving right column one step right.

right column moved right one step

Now temp row will be the sum of earlier temp row plus this column respectively..

temp += column

Now apply kadane’s 1D algo for this temp row…
So on and so forth the algorithm continues and subsequently the max subset will be obtained.

The pseudocode for this algorithm is given below.

public class ImageProcessing {

    public static Result maxSubarray2D(int[][] image) {
        if (image == null || image.length == 0 || image[0].length == 0) {
            return new Result(0, -1, -1, -1, -1);
        }

        int rows = image.length;
        int cols = image[0].length;
        int maxSum = Integer.MIN_VALUE;
        int left = -1, right = -1, top = -1, bottom = -1;

        for (int leftCol = 0; leftCol < cols; leftCol++) {
            int[] temp = new int[rows];
            
            for (int rightCol = leftCol; rightCol < cols; rightCol++) {
                for (int row = 0; row < rows; row++) {
                    temp[row] += image[row][rightCol];
                }

                Result currentResult = maxSubarray1D(temp);

                if (currentResult.sum > maxSum) {
                    maxSum = currentResult.sum;
                    left = leftCol;
                    right = rightCol;
                    top = currentResult.start;
                    bottom = currentResult.end;
                }
            }
        }

        return new Result(maxSum, left, right, top, bottom);
    }

    public static Result maxSubarray1D(int[] arr) {
        int maxSum = Integer.MIN_VALUE;
        int currentSum = 0;
        int currentStart = 0;
        int start = 0;
        int end = 0;

        for (int i = 0; i < arr.length; i++) {
            if (currentSum < 0) {
                currentSum = arr[i];
                currentStart = i;
            } else {
                currentSum += arr[i];
            }

            if (currentSum > maxSum) {
                maxSum = currentSum;
                start = currentStart;
                end = i;
            }
        }

        return new Result(maxSum, start, end);
    }

    public static class Result {
        int sum;
        int left;
        int right;
        int top;
        int bottom;

        public Result(int sum, int left, int right, int top, int bottom) {
            this.sum = sum;
            this.left = left;
            this.right = right;
            this.top = top;
            this.bottom = bottom;
        }
    }
}

Important steps to understand the whole algorithm
In 1D algorithm we will set the maxEnding to 0 whenever it goes lesser than 0.
In 2D algorithm we will set the currentSum to the current cell value whenever currentSum goes lesser that 0.

These steps have a lot of meaning inside it…
1. Handling Negative Numbers: If the array contains only negative numbers, Kadane’s algorithm ensures that the result is not a negative number. By resetting maxEnding to 0 when it becomes negative, it effectively "resets" the calculation of the maximum subarray sum at the current position. This allows the algorithm to disregard any negative prefix of the subarray and start looking for the maximum subarray sum from the current position onward.
2.Continuous Subarray Requirement: Kadane’s algorithm is designed to find a continuous subarray with the maximum sum. If the maximum subarray sum ending at a particular position becomes negative, it means that including the previous elements in the subarray would reduce its sum. Therefore, the algorithm starts looking for a new subarray by setting maxEnding to 0.

Applications

Object Detection and Tracking
Edge Detection
Image Compression
Image Enhancement
Image Analysis and Feature Extraction
Video Processing
Medical Image Analysis
Quality Control and Inspection

I hope this article gives some meaningful information to your curiosity.