Introduction

The fastest general solution for finding the contiguous integer range with the maximum sum is Kadane's algorithm. It runs in linear time, which is optimal because every element must be examined at least once. If you also need the start and end indices of the best range, you can extend the same algorithm with a few extra variables.

Why Brute Force Is Too Slow

A brute-force solution checks every possible range and sums it. That is easy to understand, but it is far too slow for large arrays.

Example brute-force shape:

1int best = int.MinValue;
2
3for (int start = 0; start < values.Length; start++)
4{
5    int sum = 0;
6    for (int end = start; end < values.Length; end++)
7    {
8        sum += values[end];
9        if (sum > best)
10        {
11            best = sum;
12        }
13    }
14}

This improved brute-force form is O(n^2). A fully naive version can be even worse. For real workloads, Kadane's algorithm is the right default.

Use Kadane's Algorithm for the Best Sum

Kadane's key idea is simple: for each position, either extend the current range or start a new range at the current element.

1using System;
2
3public static class Program
4{
5    public static int MaxSubarraySum(int[] values)
6    {
7        int current = values[0];
8        int best = values[0];
9
10        for (int i = 1; i < values.Length; i++)
11        {
12            current = Math.Max(values[i], current + values[i]);
13            best = Math.Max(best, current);
14        }
15
16        return best;
17    }
18
19    public static void Main()
20    {
21        int[] values = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
22        Console.WriteLine(MaxSubarraySum(values));
23    }
24}

This prints 6, which comes from the range [4, -1, 2, 1].

The runtime is O(n) and memory usage is O(1).

Track the Actual Range Indices

Often the sum alone is not enough. You also need the range boundaries. That can be added without changing the linear complexity.

1using System;
2
3public static class Program
4{
5    public static (int Sum, int Start, int End) MaxSubarrayRange(int[] values)
6    {
7        if (values == null || values.Length == 0)
8            throw new ArgumentException("Array must not be empty.");
9
10        int bestSum = values[0];
11        int currentSum = values[0];
12
13        int bestStart = 0;
14        int bestEnd = 0;
15        int currentStart = 0;
16
17        for (int i = 1; i < values.Length; i++)
18        {
19            if (values[i] > currentSum + values[i])
20            {
21                currentSum = values[i];
22                currentStart = i;
23            }
24            else
25            {
26                currentSum += values[i];
27            }
28
29            if (currentSum > bestSum)
30            {
31                bestSum = currentSum;
32                bestStart = currentStart;
33                bestEnd = i;
34            }
35        }
36
37        return (bestSum, bestStart, bestEnd);
38    }
39
40    public static void Main()
41    {
42        int[] values = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
43        var result = MaxSubarrayRange(values);
44        Console.WriteLine($"sum={result.Sum}, start={result.Start}, end={result.End}");
45    }
46}

This version returns both the best sum and the inclusive range that produced it.

Handle All-Negative Arrays Correctly

A common bug is returning 0 when all elements are negative. That is only correct if the problem definition allows the empty subarray. Many formulations require a non-empty range, in which case the correct answer is the least negative element.

For example:

int[] values = { -8, -3, -6, -2, -5, -4 };

The right answer is:

• sum = -2
• range = just the element at index 3

That is why robust implementations initialize from the first element instead of initializing everything to zero.

When the Problem Is Different

Kadane solves the maximum contiguous subarray problem. It does not solve:

• maximum sum of non-contiguous elements
• fixed-length window maximum sum
• maximum sum rectangle in a matrix

Those are different problems and need different algorithms. If the word "range" means contiguous segment in a one-dimensional integer array, Kadane is the standard answer.

Common Pitfalls

• Using a quadratic or cubic brute-force search when a linear algorithm exists.
• Initializing the best sum to zero and breaking all-negative input cases.
• Returning only the sum when the caller also needs the actual index range.
• Applying Kadane to a non-contiguous selection problem, which changes the problem entirely.
• Forgetting to validate empty-array input before accessing the first element.

Summary

• Kadane's algorithm is the fastest standard solution for maximum contiguous sum range in an integer array.
• It runs in O(n) time with constant extra memory.
• A few extra variables are enough to recover the start and end indices.
• Initialization from the first element is important for all-negative inputs.
• Make sure the problem really asks for a contiguous range before choosing this algorithm.