Overview

Given an integer array, find the contiguous subarray (containing at least one number) which has the largest sum, and return that sum.

Implement maxSubarraySum(nums).

This is the classic Kadane's algorithm problem — a foundational dynamic programming pattern used in financial analysis, signal processing, and performance optimization.

Constraints

• Input is a non-empty array of integers (may include negatives).
• The subarray must be contiguous and contain at least one element.
• Aim for $O(n)$ time and $O(1)$ extra space.
• Do not use brute-force $O(n^2)$ or $O(n^3)$ approaches.

Examples

maxSubarraySum([-2, 1, -3, 4, -1, 2, 1, -5, 4]);  // 6  — subarray [4, -1, 2, 1]
maxSubarraySum([1]);                                 // 1
maxSubarraySum([5, 4, -1, 7, 8]);                    // 23 — entire array
maxSubarraySum([-1, -2, -3]);                        // -1 — least negative

Notes

• Kadane's insight: at each position, either extend the current subarray or start fresh. Track the running sum and reset to the current element when the running sum drops below it.
• The global answer is the maximum running sum seen across all positions.
• Edge case: when all elements are negative, the answer is the maximum single element (the least negative).

Solution

function maxSubarraySum(nums) {
  let currentSum = nums[0];
  let maxSum = nums[0];

  for (let i = 1; i < nums.length; i++) {
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }

  return maxSum;
}

Resources

• Maximum Subarray — LeetCode
• Kadane's Algorithm — Wikipedia
• Dynamic Programming Patterns