Kadane's Algorithm Maximum Subarray in DSA Typescript

Mental Model

Find the biggest 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 stopping midway. You keep track of your current climb and reset if you start going downhill too much.

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

At each step, we track current_sum and max_sum:
current_sum ↑
max_sum ↑

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 current_sum = -2, max_sum = -2 at index 0

current_sum = -2, max_sum = -2

Why: Initialize sums with first element to start tracking

Step 2: Move to index 1: current_sum = max(1, -2 + 1) = 1, max_sum = max(-2, 1) = 1

current_sum = 1, max_sum = 1

Why: Decide to start new subarray at 1 because adding previous sum is worse

Step 3: Index 2: current_sum = max(-3, 1 + -3) = -2, max_sum = max(1, -2) = 1

current_sum = -2, max_sum = 1

Why: Current sum drops, but max_sum stays as 1

Step 4: Index 3: current_sum = max(4, -2 + 4) = 4, max_sum = max(1, 4) = 4

current_sum = 4, max_sum = 4

Why: Start new subarray at 4 since adding previous sum is worse

Step 5: Index 4: current_sum = max(-1, 4 + -1) = 3, max_sum = max(4, 3) = 4

current_sum = 3, max_sum = 4

Why: Continue current subarray, max_sum unchanged

Step 6: Index 5: current_sum = max(2, 3 + 2) = 5, max_sum = max(4, 5) = 5

current_sum = 5, max_sum = 5

Why: Add 2 to current sum, update max_sum

Step 7: Index 6: current_sum = max(1, 5 + 1) = 6, max_sum = max(5, 6) = 6

current_sum = 6, max_sum = 6

Why: Add 1 to current sum, update max_sum

Step 8: Index 7: current_sum = max(-5, 6 + -5) = 1, max_sum = max(6, 1) = 6

current_sum = 1, max_sum = 6

Why: Current sum drops but max_sum stays

Step 9: Index 8: current_sum = max(4, 1 + 4) = 5, max_sum = max(6, 5) = 6

current_sum = 5, max_sum = 6

Why: Add 4 to current sum, max_sum unchanged

Result:

Maximum subarray sum = 6

Annotated Code

DSA Typescript

class Kadane {
  static maxSubArray(nums: number[]): number {
    if (nums.length === 0) return 0;
    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;
  }
}

// Driver code
const input = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
const result = Kadane.maxSubArray(input);
console.log(`Maximum subarray sum = ${result}`);

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

Choose to start new subarray at current element or continue previous subarray

maxSum = Math.max(maxSum, currentSum);

Update maxSum if currentSum is larger

Output

Maximum subarray sum = 6

Complexity Analysis

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

Space: O(1) because we only use a few 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 with O(n)

Edge Cases

Empty array

Returns 0 as no subarray exists

DSA Typescript

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

All negative numbers

Returns the largest (least negative) single element

DSA Typescript

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

Single element array

Returns that element as max sum

DSA Typescript

let currentSum = nums[0]; let maxSum = nums[0];

When to Use This Pattern

When asked to find the maximum sum of a continuous subarray, reach for Kadane's algorithm because it efficiently tracks sums without checking all subarrays.

Common Mistakes

Mistake: Not resetting current sum when it becomes negative
Fix: Use Math.max(nums[i], currentSum + nums[i]) to decide whether to start fresh or continue

Summary

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

Use when you need the largest sum of consecutive elements efficiently.

Keep track of current sum and reset when it drops below the current element.

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