All Problems
MediumArrayDynamic ProgrammingDivide and Conquer

Maximum Subarray (Kadane's Algorithm)

Time Complexity
O(n)
Space Complexity
O(1)

📋Problem Statement

Given an integer array nums, find the subarray with the largest sum, and return its sum. A subarray is a contiguous non-empty sequence of elements within an array.

💡Examples

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 subarray [1] has the largest sum = 1.
3Example 3
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum = 23 (entire array).

⚠️Constraints

  • •1 <= nums.length <= 10^5
  • •-10^4 <= nums[i] <= 10^4

🧠Approach

This is solved using Kadane's Algorithm, a classic dynamic programming approach: **Key Insight:** At each position, we have two choices: 1. Extend the current subarray by adding the current element 2. Start a new subarray from the current element We choose whichever gives a larger sum. **Algorithm:** 1. Initialize maxSum and currentSum to the first element 2. For each subsequent element: - currentSum = max(nums[i], currentSum + nums[i]) - maxSum = max(maxSum, currentSum) 3. Return maxSum **Why It Works:** - If currentSum becomes negative, it's better to start fresh - We're essentially deciding at each step if the "past" helps or hurts

✨Solution

function maxSubArray(nums) {
    let maxSum = nums[0];
    let currentSum = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        // Either extend the current subarray or start new
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum;
}

🎯Key Points

  • 1Kadane's Algorithm is the optimal O(n) solution
  • 2Key decision: extend current subarray OR start new
  • 3If current sum goes negative, start fresh from current element
  • 4This is a foundational dynamic programming pattern
  • 5Can also be solved with divide and conquer in O(n log n)
Browse More Problems