Kadane's Algorithm Maximum Subarray in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What problem does Kadane's Algorithm solve?

Kadane's Algorithm finds the maximum sum of a contiguous subarray within a one-dimensional array of numbers.

beginner

What is the main idea behind Kadane's Algorithm?

It keeps track of the current subarray sum and resets it to zero if it becomes negative, while updating the maximum sum found so far.

intermediate

In Kadane's Algorithm, what does the variable 'currentSum' represent?

'currentSum' represents the sum of the current subarray being considered. It resets when the sum becomes negative to start fresh from the next element.

intermediate

Why does Kadane's Algorithm reset the current sum to zero when it becomes negative?

Because a negative sum will only decrease the sum of any future subarray, so it's better to start a new subarray from the next element.

beginner

What is the time complexity of Kadane's Algorithm?

Kadane's Algorithm runs in O(n) time, where n is the number of elements in the array, because it processes each element once.

What does Kadane's Algorithm find in an array?

A Maximum sum of a contiguous subarray

B Minimum element in the array

C Maximum element in the array

D Sum of all elements

Kadane's Algorithm finds the maximum sum of a contiguous subarray within the array.

What happens when the current sum becomes negative in Kadane's Algorithm?

A It doubles the sum

B It continues adding elements

C It resets to zero

D It subtracts the next element

The current sum resets to zero to start a new subarray because negative sums reduce future sums.

What is the initial value of the maximum sum in Kadane's Algorithm?

A 0

B Infinity

C First element of the array

D Negative infinity

The maximum sum starts at negative infinity to ensure any subarray sum will be larger.

What is the time complexity of Kadane's Algorithm?

A O(n)

B O(n log n)

C O(n^2)

D O(log n)

Kadane's Algorithm runs in linear time O(n), processing each element once.

Which of these is NOT part of Kadane's Algorithm?

A Tracking current subarray sum

B Sorting the array

C Resetting sum when negative

D Updating maximum sum found

Kadane's Algorithm does not sort the array; it processes elements in order.

Explain how Kadane's Algorithm finds the maximum sum of a contiguous subarray.

Think about how the algorithm decides to keep or discard parts of the subarray.

Describe why Kadane's Algorithm is efficient compared to checking all subarrays.

Compare it to the brute force approach of checking every possible subarray.

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