Medium Dynamic Programming
Maximum Subarray
Receives an array of integers and returns the sum of the contiguous subarray with the largest sum. It solves this with Kadane's algorithm — a single dynamic-programming pass that, at each index, decides whether extending the running subarray from the previous index is better than starting a new one at the current element (currentSum = max(arr[i], currentSum + arr[i])), while separately tracking the best sum seen so far. Returns that single integer, the largest sum of any contiguous subarray; an empty array returns 0.
Visualization
- Input
- Result
Algorithm code
// Maximum Subarray — a single pure function. Receives an array of integers and
// returns the sum of the contiguous subarray with the largest sum, using
// Kadane's algorithm: a single pass that tracks the best sum ending at each
// index, extending or restarting the running sum as it goes, in O(n).
/**
* @param {number[]} arr - array of integers
* @returns {number} the largest sum of any contiguous subarray (0 for an empty array)
*/
export function maxSubArray(arr) {
if (arr.length === 0) {
return 0;
}
let currentSum = arr[0];
let maxSum = arr[0];
for (let i = 1; i < arr.length; i += 1) {
currentSum = Math.max(arr[i], currentSum + arr[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}FUNCTION maxSubArray(arr):
IF length(arr) = 0:
RETURN 0
currentSum ← arr[0]
maxSum ← arr[0]
FOR i FROM 1 TO length(arr) - 1:
currentSum ← MAX(arr[i], currentSum + arr[i])
maxSum ← MAX(maxSum, currentSum)
RETURN maxSum