Why Kadane's Algorithm Maximum Subarray in DSA Javascript?

The Big Idea

What if you could find the best winning streak in your data without checking every possibility?

The Scenario

Imagine you have a list of daily profits and losses for your small business. You want to find the best continuous period where you made the most money. Doing this by checking every possible period manually would take forever!

The Problem

Manually checking every possible continuous period means looking at all combinations, which grows very fast as the list gets longer. This is slow and easy to mess up, especially if the list is big.

The Solution

Kadane's Algorithm quickly finds the best continuous period by keeping track of the current sum and the best sum found so far, without checking every combination. It does this in just one pass through the list!

Before vs After

✗ Before

let maxSum = -Infinity;
for (let i = 0; i < arr.length; i++) {
  for (let j = i; j < arr.length; j++) {
    let currentSum = 0;
    for (let k = i; k <= j; k++) {
      currentSum += arr[k];
    }
    if (currentSum > maxSum) maxSum = currentSum;
  }
}

✓ After

let maxSum = -Infinity;
let currentSum = 0;
for (let num of arr) {
  currentSum = Math.max(num, currentSum + num);
  maxSum = Math.max(maxSum, currentSum);
}

What It Enables

This algorithm lets you find the most profitable continuous period in a list quickly and easily, even if the list is very long.

Real Life Example

Stock traders use this to find the best time to buy and sell stocks by identifying the period with the highest gain.

Key Takeaways

Manual checking of all subarrays is slow and complex.

Kadane's Algorithm finds the maximum subarray sum in one pass.

It helps quickly identify the best continuous segment in data.

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