Maximum Subarray | Kadane’s Algorithm | From Brute Force to Optimal

Explore the Maximum Subarray problem with a brute-force triple loop, a quadratic improvement, and the optimal Kadane’s Algorithm, all with intuition, fully-commented Python, dry runs, and complexity analysis.

Here’s the [Problem Link] to begin with.

Find the contiguous slice of an array whose elements add up to the largest possible sum.

We’ll walk through three distinct solutions, each in its own self-contained section so you can master them one at a time:

Common Example for All Sections

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
The best subarray is [4, -1, 2, 1] with sum 6.

1. Brute Force – Triple Loop

1.1 Intuition & Approach

1. Pick every start index i.
2. Pick every end index j ≥ i.
3. Add every element from i to j in a third loop.
4. Keep the maximum sum seen.

1.2 Python Code (with comments)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxi = float("-inf")            # global best
        n = len(nums)
        for i in range(n):              # start index
            for j in range(i, n):       # end index
                cur_sum = 0
                for k in range(i, j + 1):  # walk i…j
                    cur_sum += nums[k]
                maxi = max(maxi, cur_sum)  # update best
        return maxi

1.3 Dry Run (first five iterations)

Eventually maxi becomes 6.

1.4 Complexity

• Time O(n³) – three nested loops
• Space O(1) – only scalars

Good for teaching but impractical beyond tiny arrays.

2. Better Brute – Double Loop

2.1 Intuition & Approach

Reuse the running sum s as the end index j expands; no need to recompute from scratch.

2.2 Python Code (with comments)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxi = float("-inf")
        n = len(nums)
        for i in range(n):          # start index
            s = 0
            for j in range(i, n):   # extend to the right
                s += nums[j]        # add current element
                maxi = max(maxi, s) # update best
        return maxi

2.3 Dry Run (first start index i = 0)

2.4 Complexity

• Time O(n²) – one loop dropped
• Space O(1)

A huge speed-up over triple loops, but still slow for n ≈ 10⁵.

3. Optimal – Kadane’s Algorithm

3.1 Core Insight

Maintain the best prefix sum ending at the current index.
If that prefix becomes negative, starting fresh at the next index can only help.

3.2 Algorithm Steps

1. Let curSum = 0, maxi = -∞.
2. For each element num in nums
   • curSum += num
   • maxi = max(maxi, curSum)
   • If curSum < 0, reset curSum = 0 (drop negative prefix).
3. maxi now holds the answer.

3.3 Python Code (with comments)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxi = float("-inf")   # best seen so far
        curSum = 0             # sum of current window

        for num in nums:
            curSum += num          # extend window
            maxi = max(maxi, curSum)

            if curSum < 0:         # negative drag – cut here
                curSum = 0

        return maxi

3.4 Dry Run on Example Array

3.5 Complexity

• Time O(n) – one pass
• Space O(1) – two scalars

Kadane’s Algorithm is optimal for this problem.

Summary Table

Remember the focus phrase—Maximum Subarray | Kadane’s Algorithm—and reach for Kadane to ace this classic interview favorite.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.