Maximum Subarray

Finds the contiguous subarray with the largest sum using Kadane's algorithm.

Input Array

-21-34-121-54

Step 1 of 11

Maximum Subarray (Kadane's): find the contiguous subarray with the largest sum. dp[i] = max subarray sum ending at index i.

▶Algorithm

MaxSubarray(arr):
dp[0] = arr[0]; maxSum = dp[0]
for i = 1 to n−1:
dp[i] = max(dp[i−1]+arr[i], arr[i])
maxSum = max(maxSum, dp[i])
return maxSum

Legend

Current dp cell

Dependencies

Optimal subarray

Computed

dp[i] = max subarray sum ending at index i. Extend if dp[i−1] + arr[i] > arr[i], otherwise restart.

1 / 11Speed