Maximum subarray sum
Find the largest possible sum of a non-empty contiguous subarray.
Course progress
Problem 41 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
numbers = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Expected output
6
What is happening?
The best contiguous range is [4, -1, 2, 1]. Its sum is 6, which is larger than every other contiguous range sum.
Solution strategy
Build the right mental model
At each value, decide whether to extend the current subarray or start a new one. Track the best sum seen across all ending positions.
Core concepts
dynamic programming · Kadane's algorithm
Complexity
Time O(n), space O(1).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for maximum-subarray
using System;
class Program
{
static int MaximumSubarraySum(int[] numbers)
{
if (numbers.Length == 0) throw new ArgumentException("Array cannot be empty.");
int endingHere = numbers[0];
int best = numbers[0];
for (int i = 1; i < numbers.Length; i++)
{
endingHere = Math.Max(numbers[i], endingHere + numbers[i]);
best = Math.Max(best, endingHere);
}
return best;
}
static void Main()
{
Console.WriteLine(MaximumSubarraySum(new[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 }));
}
}Knowledge check
Questions students often ask
What is the main idea behind maximum subarray sum?
At each value, decide whether to extend the current subarray or start a new one. Track the best sum seen across all ending positions.
What is the time and space complexity of this solution?
Time O(n), space O(1).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.