How do you find the maximum subarray sum (Kadane’s algorithm)?

Short answer: Kadane’s algorithm: keep a running sum; if it goes negative, reset to 0 (or start fresh at the next element). Track the best running sum seen. This finds the contiguous subarray with maximum sum in O(n).

Problem statement

Given an integer array, find the contiguous subarray with the largest sum and return that sum.

Interview approach

1. Mention divide-and-conquer O(n log n) if asked for alternatives.
2. Explain local decision: extend current subarray or start new at i.
3. Handle all-negative arrays carefully (max element, not 0).

Sample solution

int MaxSubArray(int[] nums) {
    int best = nums[0], cur = nums[0];
    for (int i = 1; i < nums.Length; i++) {
        cur = Math.Max(nums[i], cur + nums[i]);
        best = Math.Max(best, cur);
    }
    return best;
}

Complexity

Time O(n), Space O(1).

Edge cases to mention

• All negative numbers
• Single element
• Mix of positives and zeros

Common follow-ups

• Also return the start/end indices
• Circular maximum subarray

If the interviewer allows empty subarray, resetting to 0 is fine; otherwise use the version above.