Kadane's Algorithm Maximum Subarray in DSA Javascript

Mental Model

Find the largest sum of a continuous part of the list by keeping track of the best sum ending at each position.

Analogy: Imagine walking along a path with ups and downs in height. You want to find the highest hill you can climb without going back, by remembering the best climb so far and deciding if starting fresh is better.

Array: [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]
Index:  0   1   2   3   4   5   6   7   8

max_ending_here and max_so_far track sums as we move ->

Dry Run Walkthrough

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

Goal: Find the maximum sum of any continuous subarray

Step 1: Start with first element: max_ending_here = max_so_far = -2

max_ending_here = -2, max_so_far = -2

Why: Initialize sums with first element to start tracking

Step 2: Move to element 1: max_ending_here = max(1, -2 + 1) = 1; max_so_far = max(-2, 1) = 1

max_ending_here = 1, max_so_far = 1

Why: Decide to start new subarray at 1 because it is better than continuing

Step 3: Element 2: max_ending_here = max(-3, 1 + -3) = -2; max_so_far = max(1, -2) = 1

max_ending_here = -2, max_so_far = 1

Why: Continuing subarray is worse, but max_so_far stays 1

Step 4: Element 3: max_ending_here = max(4, -2 + 4) = 4; max_so_far = max(1, 4) = 4

max_ending_here = 4, max_so_far = 4

Why: Start new subarray at 4 because it is better than continuing

Step 5: Element 4: max_ending_here = max(-1, 4 + -1) = 3; max_so_far = max(4, 3) = 4

max_ending_here = 3, max_so_far = 4

Why: Continue subarray, max_so_far unchanged

Step 6: Element 5: max_ending_here = max(2, 3 + 2) = 5; max_so_far = max(4, 5) = 5

max_ending_here = 5, max_so_far = 5

Why: Continue subarray, max_so_far updated to 5

Step 7: Element 6: max_ending_here = max(1, 5 + 1) = 6; max_so_far = max(5, 6) = 6

max_ending_here = 6, max_so_far = 6

Why: Continue subarray, max_so_far updated to 6

Step 8: Element 7: max_ending_here = max(-5, 6 + -5) = 1; max_so_far = max(6, 1) = 6

max_ending_here = 1, max_so_far = 6

Why: Subarray sum drops, max_so_far stays 6

Step 9: Element 8: max_ending_here = max(4, 1 + 4) = 5; max_so_far = max(6, 5) = 6

max_ending_here = 5, max_so_far = 6

Why: Continue subarray, max_so_far unchanged

Result:

max_so_far = 6 (subarray [4, -1, 2, 1])

Annotated Code

DSA Javascript

class Kadane {
  static maxSubArray(nums) {
    if (nums.length === 0) return 0;
    let max_ending_here = nums[0];
    let max_so_far = nums[0];
    for (let i = 1; i < nums.length; i++) {
      max_ending_here = Math.max(nums[i], max_ending_here + nums[i]);
      max_so_far = Math.max(max_so_far, max_ending_here);
    }
    return max_so_far;
  }
}

// Driver code
const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(Kadane.maxSubArray(arr));

max_ending_here = Math.max(nums[i], max_ending_here + nums[i]);

Choose to start new subarray at current element or continue previous

max_so_far = Math.max(max_so_far, max_ending_here);

Update max_so_far if current subarray sum is better

Output

6

Complexity Analysis

Time: O(n) because we scan the array once, updating sums at each step

Space: O(1) because we only keep track of two variables regardless of input size

vs Alternative: Naive approach checks all subarrays with O(n^2) or O(n^3) time, Kadane's is much faster

Edge Cases

empty array

returns 0 as no subarray exists

DSA Javascript

if (nums.length === 0) return 0;

all negative numbers

returns the largest (least negative) single element

DSA Javascript

initializing max_ending_here and max_so_far with nums[0]

single element array

returns that element as max subarray sum

DSA Javascript

initializing max_ending_here and max_so_far with nums[0]

When to Use This Pattern

When you need the largest sum of a continuous part of a list, use Kadane's algorithm because it efficiently tracks the best sums without checking all subarrays.

Common Mistakes

Mistake: Not resetting max_ending_here to current element when sum becomes negative
Fix: Use max_ending_here = max(current element, max_ending_here + current element) to decide whether to start fresh

Mistake: Updating max_so_far before max_ending_here
Fix: Always update max_ending_here first, then max_so_far to reflect current best

Summary

Finds the maximum sum of any continuous subarray in a list.

Use when you want the largest sum of a contiguous part of an array efficiently.

Keep track of the best sum ending at each position and update the overall best.

Practice

1. What does Kadane's Algorithm primarily help to find in an array of numbers?

easy

A. The maximum sum of a contiguous subarray

B. The minimum element in the array

C. The total sum of all elements

D. The maximum product of any two elements

Solution

1. Step 1: Understand the problem Kadane's Algorithm solves

   Kadane's Algorithm is designed to find the maximum sum of a contiguous subarray within a one-dimensional array of numbers.

2. Step 2: Compare with other options

   Options A, B, and D describe different problems not solved by Kadane's Algorithm.

3. Final Answer:

   The maximum sum of a contiguous subarray -> Option A

4. Quick Check:

   Kadane's Algorithm = Maximum subarray sum [OK]

Hint: Kadane's finds max sum in a continuous slice [OK]

Common Mistakes:

• Confusing max sum with max product
• Thinking it finds minimum element
• Assuming it sums all elements

2. Which of the following is the correct initialization step in Kadane's Algorithm in JavaScript?

easy

A. let maxSoFar = null, maxEndingHere = null;

B. let maxSoFar = 0, maxEndingHere = 0;

C. let maxSoFar = 0, maxEndingHere = -Infinity;

D. let maxSoFar = -Infinity, maxEndingHere = 0;

Solution

1. Step 1: Understand initialization in Kadane's Algorithm

   We start with maxSoFar as the smallest possible number to handle negative values, so -Infinity is used. maxEndingHere starts at 0 to accumulate sums.

2. Step 2: Check each option

   let maxSoFar = -Infinity, maxEndingHere = 0; correctly initializes maxSoFar to -Infinity and maxEndingHere to 0. Other options either initialize incorrectly or use null which is invalid for numeric operations.

3. Final Answer:

   let maxSoFar = -Infinity, maxEndingHere = 0; -> Option D

4. Quick Check:

   Initialization = maxSoFar -Infinity, maxEndingHere 0 [OK]

Hint: Start maxSoFar at -Infinity to handle negatives [OK]

Common Mistakes:

• Initializing maxSoFar to 0 causes wrong results with negatives
• Using null instead of numbers
• Swapping initial values of variables

3. What is the output of the following JavaScript code using Kadane's Algorithm?

const arr = [-2, 3, 2, -1];
let maxSoFar = -Infinity, maxEndingHere = 0;
for (let num of arr) {
  maxEndingHere = Math.max(num, maxEndingHere + num);
  maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
console.log(maxSoFar);

medium

A. 4

B. 5

C. 3

D. 2

Solution

1. Step 1: Trace the loop iterations

   Start: maxSoFar = -Infinity, maxEndingHere = 0 - num = -2: maxEndingHere = max(-2, 0 + -2) = -2; maxSoFar = max(-Infinity, -2) = -2 - num = 3: maxEndingHere = max(3, -2 + 3) = 3; maxSoFar = max(-2, 3) = 3 - num = 2: maxEndingHere = max(2, 3 + 2) = 5; maxSoFar = max(3, 5) = 5 - num = -1: maxEndingHere = max(-1, 5 + -1) = 4; maxSoFar = max(5, 4) = 5

2. Step 2: Determine final maxSoFar value

   After the loop, maxSoFar is 5, which is the maximum sum of a contiguous subarray.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Max subarray sum = 5 [OK]

Hint: Track maxEndingHere and maxSoFar each step [OK]

Common Mistakes:

• Not updating maxSoFar correctly
• Confusing maxEndingHere with maxSoFar
• Ignoring negative numbers impact

4. Identify the bug in this Kadane's Algorithm implementation and select the fix:

function maxSubArray(arr) {
  let maxSoFar = 0;
  let maxEndingHere = 0;
  for (let i = 0; i < arr.length; i++) {
    maxEndingHere += arr[i];
    if (maxEndingHere < 0) maxEndingHere = 0;
    if (maxSoFar < maxEndingHere) maxSoFar = maxEndingHere;
  }
  return maxSoFar;
}

medium

A. Return maxEndingHere instead of maxSoFar

B. Remove resetting maxEndingHere to 0 when negative

C. Initialize maxSoFar to -Infinity to handle all negative arrays

D. Change maxEndingHere += arr[i] to maxEndingHere = arr[i]

Solution

1. Step 1: Understand the bug with initialization

   Initializing maxSoFar to 0 causes wrong results if all numbers are negative, because maxSoFar will never be less than 0.

2. Step 2: Fix initialization to handle negative arrays

   Setting maxSoFar to -Infinity allows the algorithm to correctly track the maximum subarray sum even if all elements are negative.

3. Final Answer:

   Initialize maxSoFar to -Infinity to handle all negative arrays -> Option C

4. Quick Check:

   maxSoFar init = -Infinity fixes negative array bug [OK]

Hint: Use -Infinity for maxSoFar to handle negatives [OK]

Common Mistakes:

• Leaving maxSoFar at 0 causes wrong max for negatives
• Removing reset breaks algorithm logic
• Returning wrong variable

5. Given the array [-3, -1, -2, -5], what is the maximum subarray sum using Kadane's Algorithm, and why?

hard

A. -1 because the algorithm picks the least negative single element

B. -3 because it is the first element and the algorithm stops early

C. 0 because the algorithm resets sums to zero on negatives

D. -11 because it sums all negative elements

Solution

1. Step 1: Understand Kadane's behavior with all negatives

   When all numbers are negative, Kadane's Algorithm returns the maximum single element (least negative) because any sum of multiple negatives is smaller.

2. Step 2: Identify the maximum element in the array

   Array elements: -3, -1, -2, -5. The maximum single element is -1.

3. Final Answer:

   -1 because the algorithm picks the least negative single element -> Option A

4. Quick Check:

   Max subarray sum in all negatives = max element [OK]

Hint: Max subarray in negatives = max single element [OK]

Common Mistakes:

• Assuming sum resets to zero means result is zero
• Summing all negatives incorrectly
• Stopping early without checking all elements