Explorer
Data Structures & Algorithms

Find the maximum sum of a contiguous subarray using Kadane’s algorithm.

Problem Statement

Given an integer array `nums`, find the subarray with the largest sum, and return its sum.

Examples

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output: 6

Explanation: The subarray [4, -1, 2, 1] has the largest sum 6.

Input: nums = [1]

Output: 1

Explanation: The contiguous subarray with the largest sum has a total sum of 1.

Complexity

Time Complexity: O(N)

Space Complexity: O(1)

Hints

💡 Hint 1: At each index i, we decide whether to add nums[i] to the existing running subarray sum or start a new subarray at nums[i]. 💡 Hint 2: currentSum = Math.max(nums[i], currentSum + nums[i]). 💡 Hint 3: Keep track of the global maximum maxSum seen so far.

Editorial & Approach

Problem Overview & Intuition

Kadane’s algorithm uses dynamic programming in O(1) space. At each position, a negative running sum hurts any future subarray, so if currentSum becomes negative, we reset by taking nums[i] alone.

Step-by-Step Approach

  1. Set maxSum = nums[0] and currentSum = nums[0].
  2. Iterate i from 1 to nums.length - 1.
  3. Update currentSum = Math.max(nums[i], currentSum + nums[i]).
  4. Update maxSum = Math.max(maxSum, currentSum).
  5. Return maxSum.

Optimal Implementation (JavaScript)

function maxSubArray(nums) {
  let maxSum = nums[0];
  let currentSum = 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;
}

Complexity Analysis

Time Complexity O(N) — single linear pass through the array.
Space Complexity O(1) — constant extra space.

Edge Cases & Corner Traps Handled

  • All negative numbers: correctly returns the maximum (least negative) single element.
  • Single element array: returns that element.
  • All positive numbers: returns the sum of the entire array.

Kadane's Algorithm

Medium
Given an integer array `nums`, find the subarray with the largest sum, and return its sum.
Example Scenarios
1Example 1
Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation:

The subarray [4, -1, 2, 1] has the largest sum 6.

2Example 2
Input: nums = [1]
Output: 1
Explanation:

The contiguous subarray with the largest sum has a total sum of 1.

Editor
Loading Editor...
nums =
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output:Click "Run" above to execute and verify your code here.
6