LeetCode: 'Maximum Subarray' and Kadane's Algorithm Explained

The 'Maximum Subarray' problem (LeetCode #53) is one of those classic coding challenges you'll come across, whether practising for interviews or sharpening your algorithm skills. Although it seems tricky at first glance, Kadane's Algorithm provides a simple and elegant solution that makes sense once you break it down clearly.

What Exactly is the 'Maximum Subarray' Problem?

First, let's clarify what we mean by 'Maximum Subarray'. Given an array of numbers (positive, negative, or both), our goal is to find the contiguous subarray that has the largest possible sum.

Here's a simple example:

const nums = [-2,1,-3,4,-1,2,1,-5,4];

In this array, the subarray [4, -1, 2, 1] adds up to 6, which is the largest sum possible. That's exactly what we're trying to find.

What is Kadane's Algorithm?

Kadane's Algorithm solves this problem efficiently by walking through the array just once. Instead of calculating all possible subarrays ‑ which would be very slow ‑ it cleverly keeps track of two things:

• The maximum subarray sum found so far.
• The sum of the current subarray as we move through the array.

At each step, Kadane's Algorithm clearly answers a simple question: Should we continue extending the current subarray or start fresh at the current position?

How Kadane's Algorithm Works in Practice

Let's implement this clearly in TypeScript to see it in action:

TypeScript Example of Kadane's Algorithm

const maxSubArray = (nums: number[]): number => {
  let maxSubarraySum = nums[0];
  let currentSum = nums[0];

  for (let i = 1; i < nums.length; i++) {
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSubarraySum = Math.max(maxSubarraySum, currentSum);
  }

  return maxSubarraySum;
};

const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubArray(nums));  // outputs 6

How Does This Work?

This function solves the 'Maximum Subarray' problem by using two variables:

• currentSum which keeps track of the largest sum we can achieve by including the current number.
• maxSubarraySum keeps track of the overall largest sum found so far.

For every number in the array, the algorithm asks itself a simple question: is it better to include the current number in the existing subarray, or should we start fresh from here? It picks the larger of these two choices every time. This means that we are always tracking the best possible sum at each step.

By repeatedly making this decision, the algorithm efficiently finds the highest possible sum of any contiguous subarray in just a single pass through the array.

This approach is sometimes referred to as a "greedy" solution; it focuses clearly on what's best right now without worrying too much about previous decisions.

Efficiency and Performance

Kadane's Algorithm is very efficient because it only goes through the array once:

• Time Complexity

  : O(n) (linear).

• Space Complexity

  : O(1) (constant), since we only use two extra variables.

The work grows with the number of values in the array, so a much larger input can still take noticeably longer. The useful guarantee is linear time and constant extra space, not a particular response time on every device.

Wrapping Up

Kadane's Algorithm is a great example of simplicity and effectiveness. Even though finding the maximum subarray sum sounds complicated, the algorithm solves it clearly and efficiently in just one pass. Understanding this approach doesn't just make solving the 'Maximum Subarray' problem easier, it also builds confidence when approaching similar coding challenges.

Key Takeaways

• Kadane's Algorithm finds the largest sum of any contiguous subarray efficiently.
• It keeps track of the current sum and maximum sum found so far clearly and simply.
• It visits each value once and uses constant extra space; actual runtime still depends on the input size and environment.
• Understanding how and why Kadane's works will help you approach similar algorithmic challenges confidently.

Once you're comfortable with Kadane's Algorithm, tackling similar problems starts to feel a lot less intimidating.