Kadane's Algorithm Maximum Subarray in DSA Javascript - Deep Dive

Overview - Kadane's Algorithm Maximum Subarray

What is it?

Kadane's Algorithm is a way to find the largest sum of a continuous part of a list of numbers. It looks at all possible parts but does this very fast without checking each one separately. This helps find the best section where the numbers add up to the highest value. It works even if the list has negative numbers.

Why it matters

Without Kadane's Algorithm, finding the largest sum of a continuous part would take a long time because you'd have to check every possible part. This would be slow for big lists, making programs inefficient. Kadane's Algorithm solves this by quickly finding the answer, saving time and computer power. This is important in areas like finance, gaming, or data analysis where quick decisions matter.

Where it fits

Before learning Kadane's Algorithm, you should understand arrays (lists of numbers) and basic loops. After this, you can explore related topics like dynamic programming and more complex optimization problems.

Mental Model

Core Idea

Keep track of the best sum ending at each position and update the overall best sum as you go through the list once.

Think of it like...

Imagine walking along a path with ups and downs (numbers). You want to find the best stretch where your total gain is highest. If the current stretch becomes bad, you start fresh from the next step.

Index:    0    1    2    3    4    5    6
Array:   [−2,   1,  −3,   4,  −1,   2,   1]

At each step:
Current Max Ending Here:  max( current number, current number + previous max ending here )
Overall Max So Far:       max( overall max so far, current max ending here )

Example:
Step 0: current max = -2, overall max = -2
Step 1: current max = max(1, 1 + (-2)) = 1, overall max = 1
Step 2: current max = max(-3, -3 + 1) = -2, overall max = 1
Step 3: current max = max(4, 4 + (-2)) = 4, overall max = 4
Step 4: current max = max(-1, -1 + 4) = 3, overall max = 4
Step 5: current max = max(2, 2 + 3) = 5, overall max = 5
Step 6: current max = max(1, 1 + 5) = 6, overall max = 6

Build-Up - 7 Steps

1

Foundation

Understanding the Maximum Subarray Problem

Concept: What does it mean to find the maximum sum of a continuous part of a list?

Given a list of numbers, we want to find a continuous section (subarray) where the sum of numbers is as large as possible. For example, in [1, -2, 3, 4], the subarray [3, 4] sums to 7, which is the largest possible.

Result

You understand the problem: find the continuous part with the highest sum.

Knowing the problem clearly is essential before learning how to solve it efficiently.

2

Foundation

Brute Force Approach to Maximum Subarray

Concept: Check all possible continuous parts and find the one with the largest sum.

We can try every start and end position in the list, sum the numbers in that part, and keep track of the largest sum found. This means two loops: one for start, one for end, and summing inside.

Result

This method works but takes a long time for big lists (time grows quickly).

Understanding the slow brute force method shows why a faster way is needed.

3

Intermediate

Key Idea: Tracking Current and Overall Maximum

🤔Before reading on: do you think we need to remember all sums or just some key values? Commit to your answer.

Concept: We only need to remember the best sum ending at the current position and the best sum found so far.

As we move through the list, we keep two numbers: current max sum ending here, and overall max sum. For each number, we decide if adding it to the current sum is better than starting fresh from it.

Result

This reduces the problem to a single pass through the list.

Knowing that only two values are needed simplifies the problem drastically.

4

Intermediate

Implementing Kadane's Algorithm in JavaScript

🤔Before reading on: do you think the algorithm needs nested loops or just one loop? Commit to your answer.

Concept: Use one loop to update current max and overall max sums.

Code example: const maxSubArray = (nums) => { let currentMax = nums[0]; let overallMax = nums[0]; for (let i = 1; i < nums.length; i++) { currentMax = Math.max(nums[i], currentMax + nums[i]); overallMax = Math.max(overallMax, currentMax); } return overallMax; }; Example: maxSubArray([-2,1,-3,4,-1,2,1,-5,4]) returns 6.

Result

The function returns the largest sum of any continuous subarray.

Seeing the code helps connect the idea to a working solution.

5

Intermediate

Handling Negative Numbers and Edge Cases

🤔Before reading on: do you think Kadane's Algorithm works if all numbers are negative? Commit to your answer.

Concept: Kadane's Algorithm works even if all numbers are negative by choosing the largest single number.

If all numbers are negative, the algorithm picks the least negative number as the maximum sum. This happens because currentMax compares the current number alone versus adding it to the previous sum.

Result

The algorithm correctly returns the maximum single number in all-negative lists.

Understanding this prevents confusion about algorithm failure on negative inputs.

6

Advanced

Extending Kadane's Algorithm to Find Subarray Indices

🤔Before reading on: do you think Kadane's Algorithm can tell where the max subarray starts and ends? Commit to your answer.

Concept: By tracking start and end positions along with sums, we can find the exact subarray, not just the sum.

Modify the code to keep track of the start index when currentMax resets, and update the best start and end indices when overallMax changes. Example code snippet: let start = 0, end = 0, s = 0; for (let i = 1; i < nums.length; i++) { if (nums[i] > currentMax + nums[i]) { currentMax = nums[i]; s = i; } else { currentMax += nums[i]; } if (currentMax > overallMax) { overallMax = currentMax; start = s; end = i; } } Return {maxSum: overallMax, startIndex: start, endIndex: end}.

Result

You get both the maximum sum and the exact subarray boundaries.

Knowing how to track indices makes the algorithm more practical for real problems.

7

Expert

Kadane's Algorithm in Higher Dimensions and Variants

🤔Before reading on: do you think Kadane's Algorithm can be used for 2D arrays? Commit to your answer.

Concept: Kadane's Algorithm can be extended to 2D arrays by fixing left and right columns and applying 1D Kadane on row sums between them.

For a 2D array, fix two columns and sum rows between them to create a 1D array. Then apply Kadane's Algorithm on this array to find max sub-rectangle sum. Repeat for all column pairs. This approach solves the maximum sum rectangle problem efficiently compared to brute force.

Result

You can find the maximum sum sub-rectangle in a 2D array using Kadane's Algorithm as a building block.

Understanding this extension shows the power and flexibility of the algorithm beyond simple lists.

Under the Hood

Kadane's Algorithm works by iterating once through the list, keeping track of the maximum sum of subarrays ending at each position. It uses the fact that the maximum subarray ending at position i is either the element at i alone or the element at i plus the maximum subarray ending at i-1. This avoids checking all subarrays explicitly, reducing time complexity from O(n²) to O(n).

Why designed this way?

The algorithm was designed to optimize the maximum subarray problem by using dynamic programming principles without extra space. It avoids redundant calculations by reusing previous results. Earlier methods checked all subarrays, which was too slow for large inputs. Kadane's approach balances simplicity and efficiency.

Input Array:  [a0, a1, a2, ..., an]

For each index i:
  currentMaxEndingHere = max(a[i], currentMaxEndingHere + a[i])
  overallMax = max(overallMax, currentMaxEndingHere)

Flow:
┌───────────────┐
│ Start i = 0   │
└──────┬────────┘
       │
       ▼
┌─────────────────────────────┐
│ currentMaxEndingHere = a[0] │
│ overallMax = a[0]           │
└────────────┬────────────────┘
             │
             ▼
┌─────────────────────────────────────────────┐
│ For i = 1 to n-1:                            │
│   currentMaxEndingHere = max(a[i], currentMaxEndingHere + a[i]) │
│   overallMax = max(overallMax, currentMaxEndingHere)           │
└────────────┬────────────────────────────────┘
             │
             ▼
┌───────────────┐
│ Return overallMax│
└───────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does Kadane's Algorithm always find the subarray with the most elements? Commit to yes or no.

Common Belief: Kadane's Algorithm finds the longest subarray with the maximum sum.

Reality: Kadane's Algorithm finds the subarray with the maximum sum, which may be short or long. It does not guarantee the longest subarray.

Why it matters: Assuming it finds the longest subarray can lead to wrong answers when the maximum sum is in a shorter subarray.

Quick: Can Kadane's Algorithm handle arrays with all negative numbers correctly? Commit to yes or no.

Common Belief: Kadane's Algorithm fails or returns zero when all numbers are negative.

Reality: Kadane's Algorithm correctly returns the largest (least negative) number even if all are negative.

Why it matters: Believing it fails on negatives might cause unnecessary code changes or rejection of a correct solution.

Quick: Does Kadane's Algorithm require extra memory proportional to input size? Commit to yes or no.

Common Belief: Kadane's Algorithm needs extra arrays or memory to store sums.

Reality: Kadane's Algorithm uses only a few variables and runs in constant extra space.

Why it matters: Thinking it needs extra memory can discourage its use in memory-sensitive applications.

Quick: Is Kadane's Algorithm only useful for 1D arrays? Commit to yes or no.

Common Belief: Kadane's Algorithm cannot be applied to 2D or higher-dimensional arrays.

Reality: Kadane's Algorithm can be extended to 2D arrays by applying it on row sums between column pairs.

Why it matters: Not knowing this limits the algorithm's use in more complex problems like image processing or matrix analysis.

Expert Zone

1

Kadane's Algorithm can be adapted to track the start and end indices of the maximum subarray with minimal overhead.

2

The algorithm's logic relies on the principle that a negative running sum should be reset, which is a subtle but powerful optimization.

3

In some cases, Kadane's Algorithm can be modified to handle circular arrays by combining it with total sum calculations.

When NOT to use

Kadane's Algorithm is not suitable when you need to find multiple maximum subarrays or when subarrays must meet additional constraints like fixed length. In such cases, sliding window or segment tree approaches may be better.

Production Patterns

Kadane's Algorithm is widely used in financial software to find best profit intervals, in gaming for scoring streaks, and in signal processing to detect strongest signals. It is often combined with index tracking for practical applications.

Connections

Dynamic Programming

Kadane's Algorithm is a simple form of dynamic programming that builds solutions from previous results.

Understanding Kadane's Algorithm helps grasp the core idea of dynamic programming: solving complex problems by combining solutions to smaller subproblems.

Sliding Window Technique

Both Kadane's Algorithm and sliding window optimize over subarrays but Kadane's focuses on sums with resets, while sliding window maintains a fixed or variable window.

Knowing the difference clarifies when to use each technique for efficient subarray problems.

Financial Trading Strategies

Kadane's Algorithm models finding the best time to buy and sell stocks for maximum profit, similar to finding maximum gain intervals.

Recognizing this connection shows how algorithms solve real-world problems in finance by identifying optimal intervals.

Common Pitfalls

#1 Resetting current sum incorrectly when it becomes zero instead of when negative.

Wrong approach:

if (currentMax + nums[i] < 0) {
currentMax = 0;
} else {
currentMax += nums[i];
}

Correct approach:

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

Root cause:

Misunderstanding that the reset should happen when the sum is worse than starting fresh at current element, not just when negative.

#2 Not initializing currentMax and overallMax with the first element, causing errors with negative numbers.

Wrong approach:

let currentMax = 0;
let overallMax = 0;

Correct approach:

let currentMax = nums[0];
let overallMax = nums[0];

Root cause:

Assuming sums start at zero ignores cases where all numbers are negative, leading to wrong results.

#3 Using nested loops instead of a single loop, causing slow performance.

Wrong approach:

for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
sum = 0;
for (let k = i; k <= j; k++) {
sum += nums[k];
}
// update max
}
}

Correct approach:

for (let i = 1; i < n; i++) {
currentMax = Math.max(nums[i], currentMax + nums[i]);
overallMax = Math.max(overallMax, currentMax);
}

Root cause:

Not realizing Kadane's Algorithm reduces time complexity by avoiding redundant summations.

Key Takeaways

Kadane's Algorithm finds the maximum sum of a continuous subarray in linear time by tracking the best sum ending at each position.

It works by deciding at each step whether to add the current number to the existing sum or start fresh from the current number.

The algorithm handles negative numbers gracefully by always choosing the better option between continuing or restarting the sum.

Kadane's Algorithm can be extended to find the actual subarray boundaries and to higher dimensions like 2D arrays.

Understanding Kadane's Algorithm builds a foundation for dynamic programming and efficient problem solving in many real-world applications.

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