Maximum Subarray (Kadane's Algorithm)

Problem Statement

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

Example 1:

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: Subarray [4, -1, 2, 1] has sum 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5, 4, -1, 7, 8]
Output: 23
Explanation: Entire array sums to 23.

Constraints:

• 1 <= nums.length <= 10^5.
• -10^4 <= nums[i] <= 10^4.

Difficulty: Easy / Medium LC: 53 Round: OA / Technical R1

---

Pattern Recognition

• What is the input structure? A flat integer array (may contain negatives).
• What are we optimizing? Max sum over all contiguous subarrays.
• What pattern does this fit? Kadane's algorithm — a 1D DP where curMax is the best subarray sum ending at the current index.
• Why does this pattern fit? At index i, the best subarray ending here either (a) extends the best one ending at i-1, or (b) starts fresh at nums[i]. Take the max. This local decision reduces the problem to O(n).

---

Approach

Brute Force — All Pairs

For every (i, j), compute sum(nums[i..j]) and track the max.

Time: O(n^3) naive, O(n^2) with prefix sums. Space: O(1) or O(n) for prefix sums. Why insufficient: O(n^2) is 10^10 ops for n = 10^5.

Optimal — Kadane's Algorithm

Key Insight: The best subarray ending at index i is either nums[i] alone or nums[i] appended to the best subarray ending at i-1. The global answer is the maximum such local best over all i.

Step-by-step:

1. Initialize cur = nums[0], best = nums[0].
2. For i from 1 to n-1:
   • cur = max(nums[i], cur + nums[i]).
   • best = max(best, cur).
3. Return best.

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

The decision "should I start fresh?" is encoded in the max(nums[i], cur + nums[i]) — if cur + nums[i] < nums[i], that means cur < 0, so the accumulated prefix hurts and you should reset.

---

Walkthrough

Trace on nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

Initial: cur = -2, best = -2.

i	nums[i]	cur + nums[i]	cur = max(nums[i], cur + nums[i])	best
1	1	-1	1 (restart)	1
2	-3	-2	-2 (extend)	1
3	4	2	4 (restart)	4
4	-1	3	3 (extend)	4
5	2	5	5 (extend)	5
6	1	6	6 (extend)	6
7	-5	1	1 (extend)	6
8	4	5	5 (extend)	6

Answer: 6 (subarray [4, -1, 2, 1] at indices 3..6).

Notice how at i = 3, nums[i] = 4 dominates — we restart. This corresponds to "the accumulated sum so far was -2 + 1 - 3 = -4, which hurts us more than starting fresh."

---

Implementation

TypeScript

function maxSubArray(nums: number[]): number {
    // cur = best sum of a subarray ending exactly at index i.
    let cur = nums[0];
    let best = nums[0];

    for (let i = 1; i < nums.length; i++) {
        // Extend or restart, whichever is larger.
        cur = Math.max(nums[i], cur + nums[i]);
        best = Math.max(best, cur);
    }
    return best;
}

C++

#include <vector>
#include <algorithm>

int maxSubArray(std::vector<int>& nums) {
    int cur = nums[0], best = nums[0];
    for (int i = 1; i < (int)nums.size(); i++) {
        cur = std::max(nums[i], cur + nums[i]);
        best = std::max(best, cur);
    }
    return best;
}

Watch out:

1. Initializing best = 0. For all-negative arrays, the correct answer is the least-negative single element. Seeding with 0 produces wrong answers.
2. Empty array. Problem typically guarantees n >= 1. If not, handle with if (nums.length === 0) return 0 or throw.
3. Integer overflow. For n = 10^5, max_value = 10^4, total bound 10^9 fits in int32 but is close. Use 64-bit in C++ for safety.

---

Complexity Analysis

	Time	Space
Brute Force	O(n^2)	O(1)
Optimal (Kadane)	O(n)	O(1)

Bottleneck: You must read every element. Cannot go below O(n).

---

Edge Cases

1. Single element — answer is that element.
2. All negatives — answer is the maximum (least negative) element. Kadane handles this naturally because cur and best both start at nums[0].
3. All positives — answer is the sum of the whole array. Every extend beats every restart.
4. Mixed zeros and negatives — answer is 0 if 0 appears; else the least-negative element.
5. Very large array — O(n) is still fast; no concern.

---

Related Problems

• LC 121 — Best Time to Buy and Sell Stock — Kadane in disguise: apply to the difference array.
• LC 152 — Maximum Product Subarray — Same pattern but track both min and max because negatives flip signs.
• LC 918 — Maximum Sum Circular Subarray — Kadane + "minimum subarray" trick.
• LC 1186 — Maximum Subarray Sum with One Deletion — Kadane with an extra state for "have I deleted yet?".

---

OA Strategy Notes

Trivial to implement if you know Kadane. 5 minutes. Most OAs that ask this are using it as problem 1 warmup, expecting you to submit quickly and spend remaining time on problem 2. The only trap is the all-negative edge case — verify.

---

What is Expected at Each Level

Junior: Knows Kadane by name or derives it. Implements correctly.

Mid-level: Kadane in one pass. Handles all-negative case. Mentions that Divide-and-Conquer also solves this in O(n log n) as a classic algorithm-analysis exercise.

Senior: Derives Kadane from first principles in 30 seconds. Discusses the prefix-sum formulation (best = max(prefix[j] - min(prefix[0..j-1]))). Mentions the circular-subarray variant (LC 918) and the O(1) update to handle it.