Scribd
Upload
3 views4 pages

Kadanes Algorithm Guide

Kadane's Algorithm efficiently finds the maximum sum of a contiguous subarray in O(n) time. It uses two variables to track the current and global maximum sums while iterating through the array. Variations of the algorithm include finding the actual subarray, handling all-negative numbers, and applying it to circular and 2D arrays.

Uploaded by

govindafav
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views4 pages

Kadanes Algorithm Guide

Kadane's Algorithm efficiently finds the maximum sum of a contiguous subarray in O(n) time. It uses two variables to track the current and global maximum sums while iterating through the array. Variations of the algorithm include finding the actual subarray, handling all-negative numbers, and applying it to circular and 2D arrays.

Uploaded by

govindafav
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Kadane's Algorithm - Full Guide

What is Kadane's Algorithm?

Kadane's Algorithm finds the contiguous subarray (within a one-dimensional array of numbers) that

has the largest sum.

It does this in O(n) time, which is very efficient compared to the brute-force O(n²) approach.

The Problem It Solves

Given an array of integers (positive, negative, or zero), find the maximum sum of a contiguous

subarray.

Example:

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Possible subarray: [4, -1, 2, 1] -> sum = 6

How It Works (Core Idea)

Keep two variables:

- max_current: max subarray sum ending at current position

- max_global: max subarray sum seen so far

Step-by-step:

1. Initialize max_current = max_global = arr[0]


2. Iterate through the array from index 1 to n-1:

- max_current = max(arr[i], max_current + arr[i])

- max_global = max(max_global, max_current)

Python Code (Basic Version)

def kadane(arr):

max_current = max_global = arr[0]

for i in range(1, len(arr)):

max_current = max(arr[i], max_current + arr[i])

max_global = max(max_global, max_current)

return max_global

Dry Run Example

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output: 6

Variations of Kadane's Algorithm

1. Return the actual subarray

Track start and end indices.

2. All-negative numbers

Still works. Picks the least negative.

3. Circular Array Kadane


Max of:

- Regular Kadane (no wrap)

- total_sum - min_subarray_sum

4. 2D Kadane (Max sum rectangle in matrix)

Fix left & right cols, compress rows, use 1D Kadane.

5. Kadane's for Product (Max Product Subarray)

Track both max and min product.

Summary Table

| Version | Problem | Output |

|----------------|--------------------------|-----------------|

| Basic Kadane | Max contiguous sum | Max sum |

| With Subarray | Return actual subarray | Sum + subarray |

| All Negative | Works by default | Max (least neg) |

| Circular Array | Wrap-around max sum | Max(sum, total-min) |

| 2D Kadane | Max sum submatrix | Sum |

| Product Kadane | Max contiguous product | Product |

Practice Problems

- Leetcode 53: Maximum Subarray

- Leetcode 918: Maximum Sum Circular Subarray

- Leetcode 152: Maximum Product Subarray


- InterviewBit: Max Sum Rectangle in a 2D Matrix

- Google Kickstart: Maximum Coins

You might also like