AvailablemediumDynamic Programming

Kadane's Algorithm

Master Kadane's algorithm for Maximum Subarray Sum: optimal dynamic programming state, local vs global max tracking, subarray index reconstruction, O(N) time complexity, and JavaScript implementation.

Time O(N)Space O(1)Stable YesIn-place Yes

Introduction

What is Kadane's Algorithm?

Kadane's Algorithm finds the contiguous subarray with the maximum sum in O(N) linear time and O(1) auxiliary space.

At each array element, it resolves a fundamental local DP decision: is it better to extend the existing contiguous subarray (`currentMax + num`), or discard past debt and start a fresh subarray at the current number (`num`)? By maintaining running local and global maximums, it processes the array in a single linear pass.

Algorithm Overview

How it works

1
Initialize State Variables
Set `maxSoFar = nums[0]` and `currentMax = nums[0]`. Initializing with the first element properly handles arrays containing all negative numbers.
2
Evaluate Local Choice
For each subsequent element `num`: calculate `currentMax = Math.max(num, currentMax + num)`. If `currentMax + num < num`, we start a new subarray.
3
Update Global Maximum
Update `maxSoFar = Math.max(maxSoFar, currentMax)`. Record the start and end boundary indices if subarray reconstruction is required.
4
Return Result
After completing the single O(N) scan, `maxSoFar` holds the maximum contiguous subarray sum.

maxSubArray.js

1function maxSubArray(nums) {
2  if (!nums || nums.length === 0) return 0;
3 
4  let maxSoFar = nums[0];
5  let currentMax = nums[0];
6 
7  for (let i = 1; i < nums.length; i++) {
8    // Decide whether to extend current subarray or start fresh from nums[i]
9    currentMax = Math.max(nums[i], currentMax + nums[i]);
10    maxSoFar = Math.max(maxSoFar, currentMax);
11  }
12 
13  return maxSoFar;
14}
15 
16// Extended version returning both maximum sum and subarray indices
17function maxSubArrayWithIndices(nums) {
18  let maxSoFar = nums[0];
19  let currentMax = nums[0];
20  let start = 0, end = 0, tempStart = 0;
21 
22  for (let i = 1; i < nums.length; i++) {
23    if (nums[i] > currentMax + nums[i]) {
24      currentMax = nums[i];
25      tempStart = i;
26    } else {
27      currentMax += nums[i];
28    }
29 
30    if (currentMax > maxSoFar) {
31      maxSoFar = currentMax;
32      start = tempStart;
33      end = i;
34    }
35  }
36 
37  return {
38    maxSum: maxSoFar,
39    subarray: nums.slice(start, end + 1),
40    indices: [start, end]
41  };
42}
43 
44// Example usage:
45// maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]); // 6 (Subarray: [4, -1, 2, 1])
46// maxSubArray([-5, -2, -8, -1]);               // -1 (Subarray: [-1])

Interactive Quiz

Test your knowledge

Practice Problems

Solve top interview questions

Coming Next

Interactive features on the way

The full interactive roadmap is unlocking — these specialized modules land in upcoming releases.

Next update

Interactive Subarray Highlighter

This feature will be implemented in the next update.

Next update

Running Sum Graph Plot

This feature will be implemented in the next update.

Next update

Stock Buy & Sell Price Analyzer

This feature will be implemented in the next update.

Back to all algorithms

Explore the full catalog — 30+ algorithms with more unlocking every release.

Browse Algorithms

Home/Algorithms/Kadane's Algorithm

AvailablemediumDynamic Programming

Kadane's Algorithm

Time O(N)Space O(1)Stable YesIn-place Yes

Introduction

What is Kadane's Algorithm?

Kadane's Algorithm finds the contiguous subarray with the maximum sum in O(N) linear time and O(1) auxiliary space.

Algorithm Overview

How it works

1
Initialize State Variables
Set `maxSoFar = nums[0]` and `currentMax = nums[0]`. Initializing with the first element properly handles arrays containing all negative numbers.
2
Evaluate Local Choice
For each subsequent element `num`: calculate `currentMax = Math.max(num, currentMax + num)`. If `currentMax + num < num`, we start a new subarray.
3
Update Global Maximum
Update `maxSoFar = Math.max(maxSoFar, currentMax)`. Record the start and end boundary indices if subarray reconstruction is required.
4
Return Result
After completing the single O(N) scan, `maxSoFar` holds the maximum contiguous subarray sum.

maxSubArray.js

1function maxSubArray(nums) {
2  if (!nums || nums.length === 0) return 0;
3 
4  let maxSoFar = nums[0];
5  let currentMax = nums[0];
6 
7  for (let i = 1; i < nums.length; i++) {
8    // Decide whether to extend current subarray or start fresh from nums[i]
9    currentMax = Math.max(nums[i], currentMax + nums[i]);
10    maxSoFar = Math.max(maxSoFar, currentMax);
11  }
12 
13  return maxSoFar;
14}
15 
16// Extended version returning both maximum sum and subarray indices
17function maxSubArrayWithIndices(nums) {
18  let maxSoFar = nums[0];
19  let currentMax = nums[0];
20  let start = 0, end = 0, tempStart = 0;
21 
22  for (let i = 1; i < nums.length; i++) {
23    if (nums[i] > currentMax + nums[i]) {
24      currentMax = nums[i];
25      tempStart = i;
26    } else {
27      currentMax += nums[i];
28    }
29 
30    if (currentMax > maxSoFar) {
31      maxSoFar = currentMax;
32      start = tempStart;
33      end = i;
34    }
35  }
36 
37  return {
38    maxSum: maxSoFar,
39    subarray: nums.slice(start, end + 1),
40    indices: [start, end]
41  };
42}
43 
44// Example usage:
45// maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]); // 6 (Subarray: [4, -1, 2, 1])
46// maxSubArray([-5, -2, -8, -1]);               // -1 (Subarray: [-1])

Interactive Quiz

Test your knowledge