Classic example
Input
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output
6
The contiguous subarray [4, -1, 2, 1] has the largest sum 6.
Full lesson preview
Find the maximum subarray sum
Find the largest sum of any contiguous subarray in an integer array using dynamic programming (Kadane's pattern).
Python practice15 minDynamic ProgrammingIntermediateLast updated March 29, 2026
Problem statement
Given an array of integers (which may include both positive and negative values), find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Use an O(n) time and O(1) additional space approach (Kadane's algorithm) or an equivalent dynamic programming solution. Your function should be named max_subarray_sum and accept a single list of integers, returning an integer.
Edge cases to consider: all-negative arrays, single-element arrays, large arrays.
Task
Implement an efficient function that returns the maximum sum of any contiguous subarray.
Examples
Input format
A single list of integers, e.g. [1, -2, 3, 4].
Output format
An integer representing the maximum subarray sum.
Constraints
1 <= len(nums) <= 10^5. Each element fits in a 32-bit signed integer (approx ±10^9). Aim for O(n) time.
Samples
Sample 1
Input
[1, 2, 3, 4]
Output
10
All positives, so the whole array is the max subarray.