Exercise #16: Maximum Sum Subarray by Zoran Horvat @zoranh75
Problem Statement
Given an array with N integers, write a function which finds subarray consisting of contiguous
elements of the array such that sum of elements of the subarray is maximized.
If two subarrays have the same sum, function should produce the shorter one. If
two subarrays with same sum have the same length, function should produce the
one that starts at lower array index.
Example: If array is 1 2 3 3, then largest sum subarray has length 1 and
consists only of the last array element 3. If array is 1 2 3 3 2 4, then last
three numbers (3, 2 and 4) are the largest sum subarray, with sum 5.
Problem Analysis
As the first step towards finding an efficient solution to this problem, we
might ask how many possible subarrays one array has. This would give us an idea
how to proceed in looking for the best subarray. For array consisting of N numbers, there are total of N subarrays of length 1; N1 subarrays of length 2; N2 subarrays of length 3; and so on, ending with one subarray of length N. Number of all subarrays of any length is then:
This number is not too large, but number of array elements that we touch varies
with length of the subarray. In particular, we are summing subarrays of length
1 total of N times, subarrays of length 2 total of N1 times, and so on. So total number of touches made to array elements in order
to find maximum subarray by exhausting all options is:
In this derivation we have used equations for arithmetic sequence sum and for
sum of squares, which are explained in exercises Sum of First N Numbers and Sum of Squares of First N Numbers.
The result indicates that problem can be solved by force only for reasonably
small arrays. We could iterate through all subarrays and take their sums,
looking for the one that produces largest sum. Here is the brute force
solution:
function MaxSumSubarrayForce(a, n, start out, len out)
 a  Array
 n  Length of the array
 start  On output starting position of largest subarray
 len  On output length of largest subarray
 Returns sum of the largest subarray
begin
start = 0
len = 1
sum = a[0]
for curLen = 1 to n
begin
for curStart = 1 to n  curLen + 1
begin
curSum = 0
for i = 0 to curLen  1
curSum = curSum + a[curStart + i]
if curSum > sum then
begin
start = curStart
len = curLen
sum = curSum
end
end
end
return sum
end
This function gradually increases the desired length of the subarray. For any
given length, it iterates through all subarrays of that length. Whenever a
higher sum is reached, current subarray is remembered. The one that prevails is
the overall winner.
Now that we have a dummy solution in hand, we can ask whether there is a better
one? In order to enhance running speed of the solution, we could investigate
what happens if an array is extended by one element. Suppose that we have
solved the problem for the array with N1 elements and now the Nth element is added at the end of the array. New best solution is either the
previous best, or some subarray that ends in position N1 extended by the new element. This solution requires two solutions for the
array with N1 elements: overall best subarray, and best subarray strictly ending in
position N1. With these two pieces of information, it is quite easy to determine next
best subarray. Off course, this solution requires an initial state: we are
starting with an array of length 1 and it is the best solution itself. Below is
the function which finds the largest sum subarray.
function MaxSumSubarray(a, n, start out, len out)
 a  Array
 n  Length of the array
 start  On output starting position of largest subarray
 len  On output length of largest subarray
 Returns sum of the largest subarray
begin
start = 0
len = 1
int sum = a[0]
curStart = 0
curLen = 1
curSum = a[0]
for i = 2 to n
begin
if a[i] >= curSum + a[i] then
begin
curStart = i
curLen = 1
curSum = a[i]
end
else
begin
curLen = curLen + 1
curSum = curSum + a[i]
end
if (curSum > sum) OR
(curSum = sum AND curLen < len) OR
(curSum = sum AND curLen = len AND curStart < start) then
begin
start = curStart
len = curLen
sum = curSum
end
end
return sum
end
Running time of this solution is O(N), which is significantly better than running time of the brute force
implementation, which was O(N^3). This function is the variation of Kadane's algorithm for the maximum subarray
problem.
Implementation
Below is the complete implementation of console application in C# which inputs
arrays and then produces their maximum subarrays. Note that there are slight
differences compared to the function above, because arrays in C# are
zerobased.
using System;
namespace MaximumSumSubarray
{
public class Program
{
static int[] ReadArray()
{
Console.Write("Enter array length (0 to exit): ");
int n = int.Parse(Console.ReadLine());
int[] a = null;
if (n > 0)
{
a = new int[n];
Console.Write("Enter array elements (spaceseparated): ");
string[] elements =
Console
.ReadLine()
.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
for (int i = 0; i < n; i++)
a[i] = int.Parse(elements[i]);
}
return a;
}
static int MaxSumSubarray(int[] a, out int start, out int len)
{
start = 0;
len = 1;
int sum = a[0];
int curStart = 0;
int curLen = 1;
int curSum = a[0];
for (int i = 1; i < a.Length; i++)
{
if (a[i] >= curSum + a[i])
{
curStart = i;
curLen = 1;
curSum = a[i];
}
else
{
curLen++;
curSum += a[i];
}
if ((curSum > sum) 
(curSum == sum && curLen < len) 
(curSum == sum && curLen == len && curStart < start))
{
start = curStart;
len = curLen;
sum = curSum;
}
}
return sum;
}
static void PrintArray(int[] a, int start, int len, int sum)
{
for (int i = 0; i < a.Length; i++)
{
Console.Write("{0}{1}{2}",
i == start ? '[' : ' ',
a[i],
i == start + len  1 ? ']' : ' ');
}
Console.WriteLine(" ({0})", sum);
}
static void Main(string[] args)
{
while (true)
{
int[] a = ReadArray();
if (a == null)
break;
int start = 0;
int len = 0;
int sum = MaxSumSubarray(a, out start, out len);
PrintArray(a, start, len, sum);
}
}
}
}
Demonstration
When application is run, it produces output like this:
Enter array length (0 to exit): 4
Enter array elements (spaceseparated): 1 2 3 3
1 2 3 [3] (3)
Enter array length (0 to exit): 4
Enter array elements (spaceseparated): 1 2 2 3
[1 2 2 3] (4)
Enter array length (0 to exit): 6
Enter array elements (spaceseparated): 1 2 3 3 2 4
1 2 3 [3 2 4] (5)
Enter array length (0 to exit): 6
Enter array elements (spaceseparated): 5 6 10 7 8 9
[5 6] 10 7 8 9 (11)
Enter array length (0 to exit): 7
Enter array elements (spaceseparated): 5 6 10 7 8 9 2
[5 6] 10 7 8 9 2 (11)
Enter array length (0 to exit): 0
See also:
Published: Dec 13, 2013; Modified: Dec 14, 2013
ZORAN HORVAT Zoran is software architect dedicated to clean design and CTO in a growing software company. Since 2014 Zoran is an author at Pluralsight where he is preparing a series of courses on design patterns, writing unit and integration tests and applying methods to improve code design and longterm maintainability. Follow him on Twitter @zoranh75 to receive updates and links to new articles. Watch Zoran's video courses at pluralsight.com (requires registration): Tactical Design Patterns in .NET: Managing Responsibilities Applying a design pattern to a realworld problem is not as straightforward as literature implicitly tells us. It is a more engaged process. This course gives an insight into tactical decisions we need to make when applying design patterns that have to do with separating and implementing class responsibilities. More... Tactical Design Patterns in .NET: Control Flow Improve your skills in writing simpler and safer code by applying coding practices and design patterns that are affecting control flow. More... Improving Testability Through Design This course tackles the issues of designing a complex application so that it can be covered with high quality tests. More... Share this article
