Maximum Subarray: Kadane Pattern

Learning Outcome

After this lesson, you should be able to explain why a negative running sum should be dropped and how Kadane's algorithm finds the best contiguous subarray.

Problem Statement

Given an integer array nums, return the largest possible sum of a non-empty contiguous subarray.

Brute Force Approach

Try every start index and extend to every end index while tracking the largest sum.

This is useful for understanding the problem, but it still checks too many ranges and costs O(n^2).

Optimized Approach

At each index, decide whether to extend the previous subarray or start fresh from the current number. If the previous running sum hurts the answer, drop it.

Keep two values: current, the best subarray sum ending at this index, and best, the best sum seen anywhere.

Exact Pseudocode

current = nums[0]
best = nums[0]
for i from 1 to length(nums) - 1:
  current = max(nums[i], current + nums[i])
  best = max(best, current)
return best
  

Reference Code

class Solution:
    def maxSubArray(self, nums):
        current = nums[0]
        best = nums[0]

        for value in nums[1:]:
            current = max(value, current + value)
            best = max(best, current)

        return best
  

Sample Dry Run

Complexity

Edge Cases

• All numbers are negative. Return the largest single number.
• Only one element.
• Best subarray appears at the beginning or end.

Interview Checklist

• Do not reset to zero if the problem requires a non-empty subarray.
• Explain current as "best sum ending here".
• Keep updating best after each current value.

FAQs