Kadane's Algorithm Maximum Subarray in DSA Javascript - Execution Trace

Concept Flow - Kadane's Algorithm Maximum Subarray

Start with first element

↓

Initialize current_sum and max_sum

↓

For each next element

↓

Update current_sum = max(element, current_sum + element)

↓

Update max_sum = max(max_sum, current_sum)

↓

Repeat until end of array

↓

Return max_sum

The algorithm scans the array once, keeping track of the best sum ending at each position and the overall best sum found.

Execution Sample

DSA Javascript

const arr = [-2,1,-3,4,-1,2,1,-5,4];
let current_sum = arr[0];
let max_sum = arr[0];
for(let i=1; i<arr.length; i++) {
  current_sum = Math.max(arr[i], current_sum + arr[i]);
  max_sum = Math.max(max_sum, current_sum);
}
console.log(max_sum);

Finds the maximum sum of any continuous subarray in the given array.

Execution Table

Step	Operation	Current Element	current_sum	max_sum	Subarray contributing to current_sum
1	Initialize	-2	-2	-2	[-2]
2	Process element	1	max(1, -2+1)=1	max(-2,1)=1	[1]
3	Process element	-3	max(-3,1-3)=-2	max(1,-2)=1	[-3]
4	Process element	4	max(4,-2+4)=4	max(1,4)=4	[4]
5	Process element	-1	max(-1,4-1)=3	max(4,3)=4	[4,-1]
6	Process element	2	max(2,3+2)=5	max(4,5)=5	[4,-1,2]
7	Process element	1	max(1,5+1)=6	max(5,6)=6	[4,-1,2,1]
8	Process element	-5	max(-5,6-5)=1	max(6,1)=6	[4,-1,2,1,-5]
9	Process element	4	max(4,1+4)=5	max(6,5)=6	[4,-1,2,1,-5,4]
10	End	-	-	-	-

💡 Reached end of array; max_sum = 6 is the maximum subarray sum.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	Final
current_sum	-2	1	-2	4	3	5	6	1	5	5
max_sum	-2	1	1	4	4	5	6	6	6	6

Key Moments - 3 Insights

Why do we compare current element with current_sum + element when updating current_sum?

Because if current_sum + element is less than the element alone, starting fresh from the current element gives a better sum. See execution_table rows 2 and 4 where current_sum resets.

Why do we update max_sum after updating current_sum?

Because max_sum must always hold the best sum found so far, including the new current_sum. See execution_table rows 4 to 7 where max_sum updates after current_sum.

What happens when current_sum becomes negative?

If current_sum is negative, adding next elements might reduce the sum, so we reset current_sum to the next element if it's larger. See step 3 where current_sum becomes -2 and resets at step 4.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the current_sum value?

A -2

B 4

C 3

D 1

💡 Hint

Check the 'current_sum' column at step 4 in the execution_table.

At which step does max_sum first become 6?

A Step 7

B Step 6

C Step 8

D Step 9

💡 Hint

Look at the 'max_sum' column in execution_table rows 6 to 9.

If the array started with a large positive number instead of -2, how would current_sum change at step 1?

A It would be negative

B It would be zero

C It would be that large positive number

D It would be unchanged

💡 Hint

Check variable_tracker 'current_sum' initial value and how it is set at start.

Concept Snapshot

Kadane's Algorithm finds the max sum of a continuous subarray.
Initialize current_sum and max_sum with first element.
For each element, update current_sum = max(element, current_sum + element).
Update max_sum = max(max_sum, current_sum).
Return max_sum after processing all elements.

Full Transcript

Kadane's Algorithm scans the array once, keeping track of the best sum ending at each position (current_sum) and the overall best sum found (max_sum). It starts with the first element as both current_sum and max_sum. For each next element, it decides whether to add it to the current_sum or start fresh from that element, whichever is larger. Then it updates max_sum if current_sum is better. This way, it finds the maximum sum of any continuous subarray efficiently in one pass.

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