Maximum Subarray Problem

Find the contiguous subarray with the largest sum using Divide & Conquer and Kadane's algorithm.

The Maximum Subarray Problem

Given an array of integers (possibly negative), find the contiguous subarray with the maximum sum.

Example: [-2, 1, -3, 4, -1, 2, 1, -5, 4] → The maximum subarray is [4, -1, 2, 1] with sum 6.

This classic problem has applications in stock trading (maximum profit period), image processing, and genomic sequence analysis.

Divide & Conquer Approach

Split the array at its midpoint. The maximum subarray either:

Lives entirely in the left half
Lives entirely in the right half
Crosses the midpoint

Recursively solve the left and right halves, then find the best crossing subarray by expanding outward from the midpoint in both directions. Return the maximum of all three.

Divide & Conquer Visualization

Watch the array being recursively split and merged. The crossing subarray finder scans outward from each midpoint.

0-2

2-3

4-1

7-5

Left half

Right half

Crossing

Best

Finding maximum subarray in arr[0..8] using Divide & Conquer.

1 / 34

Speed

Kadane's Algorithm (Linear Scan)

Kadane's insight: at each position, the maximum subarray ending here either extends the previous maximum subarray or starts fresh.

currentSum = max(arr[i], currentSum + arr[i])
maxSum = max(maxSum, currentSum)

If currentSum drops below the current element alone, we reset — no prefix of the subarray ending before this point helps.

Kadane's Algorithm Visualization

Watch the linear sweep across the array. The current sum tracker resets when it drops below zero, while the max sum updates whenever a new maximum is found.

0-2

2-3

4-1

7-5

-2

currentSum

-2

maxSum

Current

In subarray

Max subarray

Initialize: currentSum = maxSum = arr[0] = -2.

1 / 14

Speed

D&C vs. Kadane — Comparison

Aspect	Divide & Conquer	Kadane's Algorithm
Time	O(n log n)	O(n)
Space	O(log n) stack	O(1)
Approach	Recursive split + merge	Single linear scan
Teaching value	Shows D&C paradigm	Shows dynamic programming idea

Kadane's is faster, but the D&C approach illustrates a fundamental paradigm.

Pseudocode

Both approaches side by side.

1// Kadane's Algorithm
2KADANE(A, n)
3  maxSum = currentSum = A[1]
4  start = end = tempStart = 1
5  for i = 2 to n
6    if currentSum + A[i] < A[i]
7      currentSum = A[i]
8      tempStart = i
9    else
10      currentSum = currentSum + A[i]
11    if currentSum > maxSum
12      maxSum = currentSum
13      start = tempStart
14      end = i
15  return (maxSum, start, end)
16
17// Divide & Conquer
18MAX-SUBARRAY(A, low, high)
19  if low == high
20    return (low, high, A[low])
21  mid = (low + high) / 2
22  (lLow, lHigh, lSum) = MAX-SUBARRAY(A, low, mid)
23  (rLow, rHigh, rSum) = MAX-SUBARRAY(A, mid+1, high)
24  (cLow, cHigh, cSum) = MAX-CROSSING(A, low, mid, high)
25  return max of three by sum

Complexity Analysis

D&C: T(n) = 2T(n/2) + O(n) → O(n log n) by the Master Theorem. Kadane: single pass → O(n) with O(1) extra space.

Complexity Analysis

Time Complexity

O(n) — Kadane's / O(n log n) — D&C

Space Complexity

O(1) — Kadane's / O(log n) — D&C

Kadane's is optimal; D&C illustrates the paradigm

Growth Rate Comparison

Interactive Playground

Edit the array and compare both algorithms side by side. See how they arrive at the same answer with different strategies.

0-2

2-3

4-1

7-5

-2

currentSum

-2

maxSum

Current

In subarray

Max subarray

Initialize: currentSum = maxSum = arr[0] = -2.

1 / 14

Speed

Greedy Algorithms

Maximum Subarray Problem

Find the contiguous subarray with the largest sum using Divide & Conquer and Kadane's algorithm.

The Maximum Subarray Problem

Given an array of integers (possibly negative), find the contiguous subarray with the maximum sum.

Example: [-2, 1, -3, 4, -1, 2, 1, -5, 4] → The maximum subarray is [4, -1, 2, 1] with sum 6.

This classic problem has applications in stock trading (maximum profit period), image processing, and genomic sequence analysis.

Divide & Conquer Approach

Split the array at its midpoint. The maximum subarray either:

Lives entirely in the left half
Lives entirely in the right half
Crosses the midpoint

Recursively solve the left and right halves, then find the best crossing subarray by expanding outward from the midpoint in both directions. Return the maximum of all three.

Divide & Conquer Visualization

Watch the array being recursively split and merged. The crossing subarray finder scans outward from each midpoint.

0-2

2-3

4-1

7-5

Left half

Right half

Crossing

Best

Finding maximum subarray in arr[0..8] using Divide & Conquer.

1 / 34

Speed

Kadane's Algorithm (Linear Scan)

Kadane's insight: at each position, the maximum subarray ending here either extends the previous maximum subarray or starts fresh.

currentSum = max(arr[i], currentSum + arr[i])
maxSum = max(maxSum, currentSum)

If currentSum drops below the current element alone, we reset — no prefix of the subarray ending before this point helps.

Kadane's Algorithm Visualization

Watch the linear sweep across the array. The current sum tracker resets when it drops below zero, while the max sum updates whenever a new maximum is found.

0-2

2-3

4-1

7-5

-2

currentSum

-2

maxSum

Current

In subarray

Max subarray

Initialize: currentSum = maxSum = arr[0] = -2.

1 / 14

Speed

D&C vs. Kadane — Comparison

Aspect	Divide & Conquer	Kadane's Algorithm
Time	O(n log n)	O(n)
Space	O(log n) stack	O(1)
Approach	Recursive split + merge	Single linear scan
Teaching value	Shows D&C paradigm	Shows dynamic programming idea

Kadane's is faster, but the D&C approach illustrates a fundamental paradigm.

Pseudocode

Both approaches side by side.

1// Kadane's Algorithm
2KADANE(A, n)
3  maxSum = currentSum = A[1]
4  start = end = tempStart = 1
5  for i = 2 to n
6    if currentSum + A[i] < A[i]
7      currentSum = A[i]
8      tempStart = i
9    else
10      currentSum = currentSum + A[i]
11    if currentSum > maxSum
12      maxSum = currentSum
13      start = tempStart
14      end = i
15  return (maxSum, start, end)
16
17// Divide & Conquer
18MAX-SUBARRAY(A, low, high)
19  if low == high
20    return (low, high, A[low])
21  mid = (low + high) / 2
22  (lLow, lHigh, lSum) = MAX-SUBARRAY(A, low, mid)
23  (rLow, rHigh, rSum) = MAX-SUBARRAY(A, mid+1, high)
24  (cLow, cHigh, cSum) = MAX-CROSSING(A, low, mid, high)
25  return max of three by sum

Complexity Analysis

D&C: T(n) = 2T(n/2) + O(n) → O(n log n) by the Master Theorem. Kadane: single pass → O(n) with O(1) extra space.

Complexity Analysis

Time Complexity

O(n) — Kadane's / O(n log n) — D&C

Space Complexity

O(1) — Kadane's / O(log n) — D&C

Kadane's is optimal; D&C illustrates the paradigm

Growth Rate Comparison

Interactive Playground

Edit the array and compare both algorithms side by side. See how they arrive at the same answer with different strategies.

0-2

2-3

4-1

7-5

-2

currentSum

-2

maxSum

Current

In subarray

Max subarray

Initialize: currentSum = maxSum = arr[0] = -2.

1 / 14

Speed