Maximum Subarray (Kadane's Algorithm)

Medium

Given an integer array nums, find the subarray with the largest sum and return its sum. A subarray is a contiguous part of the array.

Examples

InputOutput
nums = [-2,1,-3,4,-1,2,1,-5,4]6
nums = [1]1

Python Solution

def max_subarray(nums: list[int]) -> int:
    best = curr = nums[0]
    for num in nums[1:]:
        curr = max(num, curr + num)
        best = max(best, curr)
    return best

JavaScript Solution

function maxSubArray(nums) {
  let best = nums[0], curr = nums[0];
  for (let i = 1; i < nums.length; i++) {
    curr = Math.max(nums[i], curr + nums[i]);
    best = Math.max(best, curr);
  }
  return best;
}

Step-by-Step Explanation

  1. Kadane's algorithm: at each position, decide whether to extend the current subarray or start fresh.
  2. curr = max(num, curr + num) — either start a new subarray or extend.
  3. best tracks the maximum sum seen so far.

Complexity Analysis

TimeO(n)
SpaceO(1)

Tags

ArrayDynamic Programming

Related Problems

Best Time to Buy and Sell StockTwo Sum

Related Tools

JSON Formatter

All Problems

Two SumReverse a StringPalindrome CheckFizzBuzzBinary SearchReverse Linked ListMerge Two Sorted ArraysValid ParenthesesRemove Duplicates from Sorted ArrayNth Fibonacci NumberValid AnagramFirst Unique CharacterClimbing StairsRoman to IntegerBest Time to Buy and Sell StockContains DuplicateMove ZeroesIntersection of Two ArraysLongest Common Prefix