Kadane's Algorithm Tutorial

Introduction

Kadane's Algorithm is an efficient method for finding the maximum sum subarray in a given array of integers. It works in linear time, making it suitable for large arrays. The algorithm is often used in various applications, such as financial analysis and computer science problems.

Problem Statement

Given an array of integers, the task is to find the contiguous subarray with the maximum sum and return this sum.

Key Concepts

• Subarray: A contiguous part of an array.
• Maximum Sum: The highest possible sum of a subarray.

Algorithm Overview

Kadane's Algorithm works by iterating through the array and maintaining two variables:

1. Current Sum (currSum): The maximum sum of the subarray that ends at the current position.
2. Global Maximum (maxSum): The maximum sum encountered so far across all subarrays.

For each element in the array, the algorithm updates currSum and maxSum as follows:

• currSum is updated to be the maximum of the current element alone or the current element plus the previous currSum.
• maxSum is updated to be the maximum of itself and currSum.

Implementation

Here’s a JavaScript implementation of Kadane's Algorithm:

const kadane1D = (nums) => {
  if (nums.length === 0) return 0;

  let currSum = nums[0];
  let maxSum = nums[0];

  for (let i = 1; i < nums.length; i++) {
    currSum = Math.max(nums[i], currSum + nums[i]);
    maxSum = Math.max(maxSum, currSum);
  }

  return maxSum;
}

// Example Usage
const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(kadane(nums)); // Output: 6 (4 + (-1) + 2 + 1)

Kadane Algorithm on 2D Grid

function kadane2D(matrix) {
  const rows = matrix.length;
  const cols = matrix[0].length;
  let maxSum = -Infinity;

  for (let topRow = 0; topRow < rows; topRow++) {
    // Initialize a 1D array to store the sum of elements between two rows
    let temp = Array(cols).fill(0);

    for (let bottomRow = topRow; bottomRow < rows; bottomRow++) {
      // Add elements between topRow and bottomRow to the temp array
      for (let col = 0; col < cols; col++) {
        temp[col] += matrix[bottomRow][col];
      }

      // Find the maximum sum subarray in this 1D array using Kadane's Algorithm
      const currentMaxSum = kadane1D(temp);
      maxSum = Math.max(maxSum, currentMaxSum);
    }
  }

  return maxSum;
}

// Example usage:
const matrix = [
  [1, 2, -1, -4, -20],
  [-8, -3, 4, 2, 1],
  [3, 8, 10, 1, 3],
  [-4, -1, 1, 7, -6]
];

console.log(kadane2D(matrix)); // Output: 29 (submatrix from (1, 1) to (3, 3))