Kadane's Algorithm Maximum Subarray in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kadane's Algorithm on Mixed Array

What is the output of the following JavaScript code that uses Kadane's Algorithm to find the maximum subarray sum?

DSA Javascript

function maxSubArray(nums) {
  let maxSoFar = nums[0];
  let maxEndingHere = nums[0];
  for (let i = 1; i < nums.length; i++) {
    maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
    maxSoFar = Math.max(maxSoFar, maxEndingHere);
  }
  return maxSoFar;
}

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

A 7

B 6

C 5

D 4

💡 Hint

Focus on how the algorithm updates the current sum and the maximum sum found so far.

Kadane's algorithm finds the maximum sum of a contiguous subarray. For the input array, the maximum sum subarray is [4, -1, 2, 1] which sums to 6.

❓ Predict Output

intermediate

Maximum Subarray Sum for All Negative Numbers

What will be the output of this Kadane's Algorithm implementation when all numbers are negative?

DSA Javascript

function maxSubArray(nums) {
  let maxSoFar = nums[0];
  let maxEndingHere = nums[0];
  for (let i = 1; i < nums.length; i++) {
    maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
    maxSoFar = Math.max(maxSoFar, maxEndingHere);
  }
  return maxSoFar;
}

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

A -4

B -3

C -8

D -2

💡 Hint

Kadane's algorithm returns the largest single element if all are negative.

When all numbers are negative, the maximum subarray is the single largest number, which is -2 here.

🧠 Conceptual

advanced

Understanding Kadane's Algorithm Variables

In Kadane's Algorithm, what does the variable 'maxEndingHere' represent during the iteration?

A The maximum sum of a subarray that ends at the current index

B The maximum sum of any subarray found so far in the entire array

C The sum of all elements in the array up to the current index

D The minimum sum of a subarray that starts at the current index

💡 Hint

Think about how the algorithm decides to continue or start a new subarray at each step.

'maxEndingHere' keeps track of the best sum of a subarray that ends exactly at the current position, helping decide whether to extend or start fresh.

❓ Predict Output

advanced

Output of Kadane's Algorithm with Single Element Array

What is the output of the following code when the input array has only one element?

DSA Javascript

function maxSubArray(nums) {
  let maxSoFar = nums[0];
  let maxEndingHere = nums[0];
  for (let i = 1; i < nums.length; i++) {
    maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
    maxSoFar = Math.max(maxSoFar, maxEndingHere);
  }
  return maxSoFar;
}

console.log(maxSubArray([10]));

A NaN

B 0

C 10

D undefined

💡 Hint

Consider how the algorithm initializes variables and the loop behavior with a single element.

With one element, the maximum subarray sum is the element itself, 10.

❓ Predict Output

expert

Maximum Subarray Sum with Zeroes and Positives

What is the output of this Kadane's Algorithm code for the input array containing zeroes and positive numbers?

DSA Javascript

function maxSubArray(nums) {
  let maxSoFar = nums[0];
  let maxEndingHere = nums[0];
  for (let i = 1; i < nums.length; i++) {
    maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
    maxSoFar = Math.max(maxSoFar, maxEndingHere);
  }
  return maxSoFar;
}

console.log(maxSubArray([0, 0, 5, 0, 3, 0, 2]));

A 10

B 5

C 3

D 0

💡 Hint

Sum the contiguous subarray with the largest total including zeroes.

The maximum subarray is [5, 0, 3, 0, 2] which sums to 10.

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