Kadane's Algorithm Maximum Subarray in DSA Typescript - 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 each number and decides whether to add it to the current sum or start fresh from that number. This helps find the maximum sum quickly without checking every possible part. 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 lot of time, especially for big lists, because you'd have to check all parts. This algorithm makes it fast and efficient, saving time and computer power. It helps in many real-world problems like finding the best time to buy and sell stocks or analyzing signals.

Where it fits

Before learning Kadane's Algorithm, you should understand arrays and basic loops. After this, you can explore more complex algorithms for subarray problems, like divide and conquer or dynamic programming techniques for related challenges.

Mental Model

Core Idea

At each step, decide whether to continue the current sum or start a new sum from the current number to find the maximum continuous sum.

Think of it like...

Imagine walking along a path where some steps give you energy and some take it away. You want to find the longest stretch where your energy gain is the highest. Sometimes it's better to start fresh from a new step if the current energy is too low.

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

At each index:
Current Sum: max(current number, current sum + current number)
Max Sum So Far: max(max sum so far, current sum)

Flow example:
Index 0: current sum = -2, max sum = -2
Index 1: current sum = max(1, -2+1)=1, max sum=1
Index 2: current sum = max(-3,1-3)=-2, max sum=1
Index 3: current sum = max(4,-2+4)=4, max sum=4
Index 4: current sum = max(-1,4-1)=3, max sum=4
Index 5: current sum = max(2,3+2)=5, max sum=5
Index 6: current sum = max(1,5+1)=6, max sum=6
Index 7: current sum = max(-5,6-5)=1, max sum=6
Index 8: current sum = max(4,1+4)=5, max sum=6

Build-Up - 7 Steps

1

Foundation

Understanding the Maximum Subarray Problem

Concept: Learn what the maximum subarray problem is and why it matters.

Given a list of numbers, the maximum subarray problem asks: which continuous part of this list has the largest sum? For example, in [1, -2, 3, 4, -1], the subarray [3, 4] has the largest sum 7. The problem is to find this sum quickly.

Result

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

Knowing the problem clearly helps you see why a fast solution is needed instead of checking all parts.

2

Foundation

Brute Force Approach to Maximum Subarray

Concept: Try all possible continuous parts and find their sums to get the maximum.

Check every possible start and end position in the list. For each, sum the numbers and keep track of the largest sum found. This takes a lot of time because the number of parts grows quickly with the list size.

Result

For list [1, -2, 3, 4, -1], brute force finds max sum 7 by checking all parts.

Seeing the brute force method shows why a faster way is needed for big lists.

3

Intermediate

Key Idea Behind Kadane's Algorithm

🤔Before reading on: do you think adding a negative number always lowers the sum or can it sometimes help? Commit to your answer.

Concept: At each number, decide whether to add it to the current sum or start fresh from it.

Keep a running sum of numbers. If adding the current number makes the sum smaller than the number itself, start a new sum from the current number. Keep track of the largest sum seen so far.

Result

You can find the maximum sum in one pass through the list.

Understanding this decision at each step is the heart of Kadane's Algorithm and why it is efficient.

4

Intermediate

Implementing Kadane's Algorithm in TypeScript

🤔Before reading on: do you think Kadane's Algorithm needs extra space proportional to input size or just a few variables? Commit to your answer.

Concept: Write code that uses two variables to track current sum and max sum while looping once through the list.

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

Result

The function returns the maximum subarray sum efficiently.

Knowing Kadane's Algorithm uses constant space and one pass makes it practical for large data.

5

Intermediate

Handling All Negative Numbers Case

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

Concept: Kadane's Algorithm still works if all numbers are negative because it picks the largest single number as max sum.

If the list is [-3, -5, -2, -8], the algorithm picks -2 as the max sum because starting fresh at each number chooses the largest number when sums are negative.

Result

The algorithm returns the largest negative number as max sum.

Understanding this edge case shows Kadane's Algorithm is robust and does not fail with negative inputs.

6

Advanced

Tracking the Maximum Subarray Indices

🤔Before reading on: do you think Kadane's Algorithm can be modified to find the start and end positions of the max subarray? Commit to your answer.

Concept: By remembering where the current sum started and updating max start/end when max sum changes, we can find the subarray boundaries.

Add variables start, end, and tempStart. When currentSum resets to nums[i], set tempStart = i. When maxSum updates, set start = tempStart and end = i. Example code snippet: let start = 0, end = 0, tempStart = 0; for (let i = 1; i < nums.length; i++) { if (nums[i] > currentSum + nums[i]) { currentSum = nums[i]; tempStart = i; } else { currentSum += nums[i]; } if (currentSum > maxSum) { maxSum = currentSum; start = tempStart; end = i; } } Return maxSum and indices [start, end].

Result

You get both the maximum sum and the exact subarray that produces it.

Knowing how to track indices extends Kadane's Algorithm from just sums to actual subarrays, useful in many applications.

7

Expert

Kadane's Algorithm in Higher Dimensions and Variants

🤔Before reading on: do you think Kadane's Algorithm can be directly applied to 2D arrays or does it need changes? 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 left and right. Sum rows between these columns into a temporary array. Run 1D Kadane on this array to find max subarray sum for these columns. Repeat for all column pairs to find max 2D subarray sum. This approach runs in O(n^3) time for an n x n matrix. Variants include finding max product subarray or handling circular arrays with modifications.

Result

You can solve more complex maximum subarray problems beyond 1D using Kadane's idea.

Understanding these extensions shows Kadane's Algorithm is a powerful pattern, not just a single trick.

Under the Hood

Kadane's Algorithm works by maintaining a running sum of the current subarray. At each element, it decides whether to add the element to the current sum or start a new sum from that element. This decision is based on which choice yields a larger sum. Internally, it uses two variables updated in a single pass, making it very efficient in time and space.

Why designed this way?

The algorithm was designed to avoid the costly brute force approach that checks all subarrays. By using a greedy approach that locally optimizes at each step, it achieves a global optimum. Alternatives like divide and conquer exist but are more complex and slower in practice.

Start -> [Initialize currentSum = first element, maxSum = first element]
  |
  v
Loop over elements from second to last:
  |
  v
Decision: currentSum = max(current element, currentSum + current element)
  |
  v
Update maxSum = max(maxSum, currentSum)
  |
  v
End -> maxSum is maximum subarray sum

Myth Busters - 4 Common Misconceptions

Quick: Does Kadane's Algorithm always find the longest maximum sum subarray? Commit yes or no.

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

Reality: Kadane's Algorithm finds a maximum sum subarray but not necessarily the longest one if multiple subarrays have the same max sum.

Why it matters: Assuming it finds the longest can lead to wrong answers when subarray length matters, requiring extra logic.

Quick: Can Kadane's Algorithm be used directly on arrays with all negative numbers? Commit 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 negative number as the max sum even if all are negative.

Why it matters: Misunderstanding this leads to incorrect handling of negative-only inputs and bugs.

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

Common Belief: Kadane's Algorithm needs extra arrays or memory proportional to the input size.

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

Why it matters: Thinking it needs extra memory may discourage its use in memory-sensitive environments.

Quick: Is Kadane's Algorithm a dynamic programming solution? Commit yes or no.

Common Belief: Kadane's Algorithm is not dynamic programming; it's just a greedy approach.

Reality: Kadane's Algorithm is a form of dynamic programming because it builds the solution using previous results.

Why it matters: Recognizing it as dynamic programming helps understand its relation to other DP problems and techniques.

Expert Zone

1

Kadane's Algorithm can be adapted to track multiple maximum subarrays if they have the same sum, but this requires careful bookkeeping.

2

The algorithm's greedy step relies on the fact that local optimal decisions lead to a global optimum only because of the problem's structure; this does not hold for all maximum subarray variants.

3

In streaming or online scenarios, Kadane's Algorithm can be used incrementally, but resetting the current sum correctly is crucial to avoid errors.

When NOT to use

Kadane's Algorithm is not suitable when you need the longest maximum sum subarray or when subarrays must satisfy additional constraints like length limits or non-continuous elements. For such cases, segment trees, divide and conquer, or sliding window techniques are better.

Production Patterns

Kadane's Algorithm is widely used in financial software to find best profit intervals, in signal processing to detect strongest signals, and in competitive programming as a fundamental technique for subarray problems. It is often combined with index tracking to return subarray boundaries.

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 problems by combining solutions to smaller subproblems.

Sliding Window Technique

Both Kadane's Algorithm and sliding window handle subarrays, but sliding window is for fixed or constrained sizes while Kadane's finds max sum without size limits.

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

Financial Trading Strategies

Kadane's Algorithm models finding the best time to buy and sell stocks by identifying maximum profit intervals.

Seeing this connection shows how abstract algorithms solve real-world money problems.

Common Pitfalls

#1 Starting current sum at zero instead of first element causes wrong results when all numbers are negative.

Wrong approach:

let currentSum = 0;
let maxSum = Number.NEGATIVE_INFINITY;
for (let num of nums) {
currentSum = Math.max(num, currentSum + num);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;

Correct approach:

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

Root cause:

Initializing currentSum to zero ignores the first element and breaks correctness when all elements are negative.

#2 Trying to find max subarray by summing all positive numbers only, ignoring negative numbers that might be needed to connect subarrays.

Wrong approach:

let maxSum = 0;
for (let num of nums) {
if (num > 0) maxSum += num;
}
return maxSum;

Correct approach:

Use Kadane's Algorithm to consider negative numbers properly and find the true maximum sum subarray.

Root cause:

Ignoring negative numbers misses subarrays where including negatives leads to a larger total sum.

#3 Not updating maxSum after updating currentSum leads to incorrect max sum.

Wrong approach:

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

Correct approach:

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

Root cause:

Failing to track maxSum means the algorithm returns the last currentSum, not the maximum found.

Key Takeaways

Kadane's Algorithm efficiently finds the maximum sum of a continuous subarray in linear time using constant space.

At each step, it decides whether to continue the current sum or start fresh, which is the key to its speed and correctness.

It works correctly even when all numbers are negative by choosing the largest single number.

The algorithm can be extended to track the subarray indices and to higher dimensions like 2D arrays.

Understanding Kadane's Algorithm deepens your grasp of dynamic programming and greedy strategies for optimization problems.

Practice

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

easy

A. The number of positive elements

B. The minimum element in the array

C. The total sum of all elements

D. The maximum sum of a contiguous subarray

Solution

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

   Kadane's Algorithm is designed to find the maximum sum of any contiguous subarray within a given array.

2. Step 2: Differentiate from other array operations

   It does not find minimum elements, total sum, or count positives, but specifically the largest sum of a continuous segment.

3. Final Answer:

   The maximum sum of a contiguous subarray -> Option D

4. Quick Check:

   Maximum subarray sum = The maximum sum of a contiguous subarray [OK]

Hint: Kadane finds max sum in continuous parts of array [OK]

Common Mistakes:

• Confusing max sum with total sum of array
• Thinking it finds minimum values
• Assuming it counts positive numbers

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

easy

A. let maxSoFar = Number.MIN_SAFE_INTEGER, maxEndingHere = 0;

B. let maxSoFar = [], maxEndingHere = [];

C. let maxSoFar = 0, maxEndingHere = 0;

D. let maxSoFar = null, maxEndingHere = null;

Solution

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

   We initialize maxSoFar to the smallest safe integer to handle arrays with negative numbers correctly, and maxEndingHere to 0.

2. Step 2: Check each option's correctness

   let maxSoFar = Number.MIN_SAFE_INTEGER, maxEndingHere = 0; correctly uses Number.MIN_SAFE_INTEGER for maxSoFar and 0 for maxEndingHere. Other options use incorrect types or values.

3. Final Answer:

   let maxSoFar = Number.MIN_SAFE_INTEGER, maxEndingHere = 0; -> Option A

4. Quick Check:

   Initialization with min safe integer = let maxSoFar = Number.MIN_SAFE_INTEGER, maxEndingHere = 0; [OK]

Hint: Initialize maxSoFar with smallest integer to handle negatives [OK]

Common Mistakes:

• Initializing maxSoFar to 0 causes wrong results with all negatives
• Using arrays instead of numbers for maxSoFar
• Setting variables to null instead of numbers

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

function maxSubArray(nums: number[]): number {
  let maxSoFar = Number.MIN_SAFE_INTEGER;
  let maxEndingHere = 0;
  for (const num of nums) {
    maxEndingHere = Math.max(num, maxEndingHere + num);
    maxSoFar = Math.max(maxSoFar, maxEndingHere);
  }
  return maxSoFar;
}

console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]));

medium

A. 6

B. 7

C. 5

D. 4

Solution

1. Step 1: Trace the Kadane's Algorithm on the input array

   Iterate through [-2,1,-3,4,-1,2,1,-5,4]: max subarray sums update as -2,1, -2,4,3,5,6,1,5.

2. Step 2: Identify the maximum sum found

   The maximum sum found during iteration is 6, which corresponds to subarray [4,-1,2,1].

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Max subarray sum = 6 [OK]

Hint: Track maxEndingHere and maxSoFar updates carefully [OK]

Common Mistakes:

• Adding all positive numbers only
• Ignoring negative numbers impact
• Confusing maxSoFar with maxEndingHere

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

function maxSubArray(nums: number[]): number {
  let maxSoFar = 0;
  let maxEndingHere = 0;
  for (const num of nums) {
    maxEndingHere = Math.max(num, maxEndingHere + num);
    maxSoFar = Math.max(maxSoFar, maxEndingHere);
  }
  return maxSoFar;
}

medium

A. Remove resetting maxEndingHere to 0 when negative

B. Initialize maxSoFar with Number.MIN_SAFE_INTEGER instead of 0

C. Change maxEndingHere += num to maxEndingHere = num

D. Return maxEndingHere instead of maxSoFar

Solution

1. Step 1: Analyze initialization problem

   Initializing maxSoFar to 0 causes wrong results if all numbers are negative, as maxSoFar never updates below 0.

2. Step 2: Fix initialization to handle negative arrays

   Setting maxSoFar to Number.MIN_SAFE_INTEGER allows correct tracking of max sums even if all are negative.

3. Final Answer:

   Initialize maxSoFar with Number.MIN_SAFE_INTEGER instead of 0 -> Option B

4. Quick Check:

   Proper initialization fixes negative-only arrays [OK]

Hint: Use smallest integer for maxSoFar to handle negatives [OK]

Common Mistakes:

• Leaving maxSoFar as 0 causes wrong max for negatives
• Removing reset of maxEndingHere breaks algorithm logic
• Returning wrong variable from function

5. Given an array of integers, how can Kadane's Algorithm be adapted to also return the start and end indices of the maximum sum subarray?
Choose the correct approach.

hard

A. Use two nested loops to find max sum and indices

B. Store all subarrays and pick the max sum one at the end

C. Track start index when maxEndingHere resets; update end index when maxSoFar updates

D. Return the first positive element's index as start and end

Solution

1. Step 1: Understand Kadane's Algorithm extension for indices

   When maxEndingHere resets to current element, update start index; when maxSoFar updates, update end index to current position.

2. Step 2: Compare with other approaches

   Storing all subarrays or using nested loops is inefficient; returning first positive index is incorrect.

3. Final Answer:

   Track start index when maxEndingHere resets; update end index when maxSoFar updates -> Option C

4. Quick Check:

   Index tracking with resets and updates = Track start index when maxEndingHere resets; update end index when maxSoFar updates [OK]

Hint: Update start on reset, end on max update for indices [OK]

Common Mistakes:

• Using nested loops loses Kadane's efficiency
• Ignoring index updates when maxEndingHere resets
• Assuming first positive element is max subarray start