Learn
Kadane's Algorithm
Kadane's Algorithm finds the maximum sum of any contiguous subarray in time with a single pass. It's a classic example of dynamic programming with space.
At each position, you decide whether to extend the previous subarray or start a new one. You extend if the previous sum is positive.
text
function maxSubarraySum(arr, n):
maxSum = arr[0]
currentSum = arr[0]
for i from 1 to n - 1:
currentSum = max(arr[i], currentSum + arr[i])
maxSum = max(maxSum, currentSum)
return maxSum
If your becomes negative, starting fresh at the current element is always better than carrying the negative sum forward.
Tracking the subarray: To find the actual subarray indices, track start and end positions:
text
function maxSubarrayWithIndices(arr, n):
maxSum = arr[0]
currentSum = arr[0]
start = 0
end = 0
tempStart = 0
for i from 1 to n - 1:
if arr[i] > currentSum + arr[i]:
currentSum = arr[i]
tempStart = i
else:
currentSum = currentSum + arr[i]
if currentSum > maxSum:
maxSum = currentSum
start = tempStart
end = i
return (maxSum, start, end)
Applications: You use Kadane's algorithm for stock trading (max profit), signal processing, image processing, and finding optimal subarrays.
Time complexity: with a single pass through the array.
Space complexity: using only a few variables.