Kadane’s Algorithm: Maximum Subarray Sum Using Linear Scan

In our previous post, we explored the Linear Scan pattern — a simple yet powerful technique where we traverse an array once to find a solution efficiently. Today, we’ll see a problem where linear scanning meets clever state management: finding the maximum subarray sum, famously solved by Kadane’s Algorithm.

Problem

Given an array of integers, we want to find the contiguous subarray with the largest sum

Input: arr = [1, -2, 3, 5, -3, 2]
Output: 8
Explanation: The maximum sum subarray is [3, 5], sum = 8

Edge Cases: Kadane’s Little Adventures

1. All Negative Numbers – The Pessimist’s Array

Even when every number is a loss, Kadane finds the least bad.

arr = [-5, -2, -8, -1] → max subarray sum = -1 code

2.Single Element Array – The Lone Hero

When there’s only one number, it stands alone as the maximum.

arr = [7] → max subarray sum = 7

3.Empty Array – The Invisible Challenge

No numbers? No problem. Kadane gracefully returns null, showing nothing to compute.

arr = [] → max subarray sum = null

Kadane adapts to every scenario, proving that whether the array is pessimistic, tiny, or invisible, it always finds the best outcome.

Naive Approach – The Backroads

At first, we could check every possible subarray, sum them, and pick the largest. It works, but it’s like taking every little backroad to reach a destination — slow and exhausting.

Now imagine a smarter way: as we walk through the array, we carry a running sum, deciding at each step whether to extend our current path or start fresh. That’s the linear scan with dynamic running state, the magic behind Kadane’s Algorithm — a fast highway to the maximum subarray sum.

The Kadane’s Algorithm Idea – Walking the Highway

Imagine you’re walking along a long road of numbers. Your goal? Find the longest stretch with the highest “happiness” (sum).

1.Carry a running score (currentSum)

currentSum = max(num, currentSum + num)

2.Remember the best stretch (maxSoFar)

maxSoFar = max(maxSoFar, currentSum)

At the end of the road, maxSoFar holds the maximum happiness — the maximum subarray sum.

Kadane’s Algorithm – Step-by-Step Flow

Start
  │
  ▼
Initialize currentSum = arr[0], maxSoFar = arr[0]
  │
  ▼
For each element num in arr[1..n-1]
  │
  ▼
  ┌───────────────────────────────┐
  │ currentSum = max(num, currentSum + num) │
  └───────────────────────────────┘
  │
  ▼
  ┌─────────────────────┐
  │ maxSoFar = max(maxSoFar, currentSum) │
  └─────────────────────┘
  │
  ▼
End of loop?
  │
 ┌─┴─┐
Yes │ No
 └─┬─┘
   │
   ▼
Return maxSoFar
   │
   ▼
  End

1. **Initialize:**
   - currentSum = arr[0]
   - maxSoFar = arr[0]

2. **Iterate through the array** from index 1 to end:
   - For each element `num`:
       - Update currentSum = max(num, currentSum + num) → decide to **extend** the current subarray or **start a new subarray**
       - Update maxSoFar = max(maxSoFar, currentSum) → track the **global maximum**

3. **Return maxSoFar** as the maximum subarray sum

Kotlin Implementation

fun kadanesMaxSubArray(inputs: IntArray): Int? {
    if (inputs.isEmpty()) return null
    var maxSoFar = inputs[0]
    var currentSum = inputs[0]
    for (i in 1  until inputs.size) {
        currentSum = maxOf(inputs[i], currentSum + inputs[i])
        maxSoFar = maxOf(maxSoFar, currentSum)
    }
    return maxSoFar
}

Insights

Why linear scan works:

We don’t need to remember sums of all previous subarrays—just the sum of the current subarray (currentSum) is enough. This is why we can solve the problem in a single pass through the array.

Handles negative numbers naturally:

The algorithm automatically deals with negative numbers. If adding a new element makes the current sum smaller than the element itself, we start a new subarray. This ensures that negative numbers don’t break the calculation.

Efficient performance:

Time complexity: O(n), because we only loop through the array once.

Space complexity: O(1), because we only need a couple of variables (currentSum and maxSoFar) instead of storing multiple subarray sums.

Tracking the subarray itself:

It’s possible to not only find the maximum sum but also remember the starting and ending indices of the subarray that gives this sum. This requires a few extra variables but uses the same linear scan approach.

Real-World Applications

Conclusion

Kadane’s Algorithm beautifully demonstrates how a simple linear scan can be enhanced with state tracking to solve non-trivial problems efficiently. By keeping track of just the current sum and the maximum so far, we can handle negative numbers, large arrays, and even find the exact subarray that gives the maximum sum.

Understanding this pattern is valuable in many real-world scenarios, from financial data analysis to performance analytics, where quick, efficient computations are crucial.

Thank you for following along! Keep practicing these patterns—they form the foundation for solving many algorithmic problems elegantly. Remember, sometimes the simplest approach with a little smart tracking is all you need.

Happy coding! 🚀