Chapter 7: Maximum Subarray Problem
1. Introduction
Given an integer array, which contains positive and negative numbers. Find the contiguous subarray which has the largest sum. The time complexity should be O(N).
For example, for the sequence of values 1, -2, 3, 10, -4, 7, 2, -5, the contiguous subarray with the largest sum is 3, 10, -4, 7, 2, with sum 18.
2. Solution Ideas
2.1 Brute Force
To find the subarray with the largest sum, we can easily come up with a brute force solution. That is, use three for loops to traverse through the array and compute the sum of each subarray. Each time we get a sum, we will update current maximum sum if the new sum is greater. So let Sum[i..j] be the sum of the ith element all through the jth element (0 <= i <= j < n). To traverse through all possible Sum[i..j], the time complexity would be O(N^3):
// This code fragment was a quote from Beauty of Programming
int MaxSum(int* A, int n)
{
int maximum = -INF;
int sum = 0;
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
for (int k = i; k <= j; k++)
{
sum += A[k];
}
if (sum > maximum)
maximum = sum;
sum = 0; // reset it to 0, or sum would be the sum of all subarrays.
}
}
return maximum;
}
2.2 O(N) Solution
#include <iostream.h>
int maxSum(int* a, int n)
{
int sum = 0;
// Change this to "int sum = a[0]" when all is negtive
// you can also leave it as it is as well, it simply returns 0.
int b = 0;
for (int i = 0; i < n; i++)
{
if (b < 0)
b = a[i];
else
b += a[i];
if (sum < b)
sum = b;
}
return sum;
}
int main()
{
int a[10] = {1, -2, 3, 10, -4, 7, 2, -5};
//int a[] = {-1,-2,-3,-4}; // for the case when all integers are negative
cout << maxSum(a, 8) << endl;
return 0;
}
/*-------------------------------------
Explanation:
If the input array is: 1, -2, 3, 10, -4, 7, 2, -5，
then the subarray with largest sum is 3, 10, -4, 7, 2，
So the output should be 18.
All is shown in the following two lines,
b ： 0 1 -1 3 13 9 16 18 13
sum： 0 1 1 3 13 13 16 18 18
In effect, after the previous several numbers
was added up, if b < 0, set b to next element, b = a[i].
Then compare b with sum:
if b > sum, sum = b;
if b < sum, leave sum as it is.
----------------------------------*/
2.3 A Revised O(N) Solution
You may notice that the solution does not take the case when all integers are negative into consideration. So we can either return 0 or return the largest negtive one in the array to handle this case, here is a revised version:
#include <iostream.h>
#define n 4 // we define an additional variable for testing
int maxsum(int a[n])
// here, you can see strength when using pointer in case 2
{
int max = a[0]; // return the largest one in the all-negative case
int sum = 0;
for (int j = 0; j < n; j++)
{
if (sum >= 0) // after add a previous element, if sum >= 0, add this one
sum += a[j];
else
sum = a[j]; // or, do not add, simply set sum to this element
if (sum > max)
max = sum;
}
return max;
}
int main()
{
int a[] = { -1, -2, -3, -4};
cout << maxsum(a) << endl;
return 0;
}
2.4 Dynamic Programming
Let sum[i] be the subarray with largest sum of the first i elements, let result be the subarray with largest sum we know so far. For the i+1th element, either append it to the former subarray we've found or let it be the first element of the new subarray.
sum[i+1] = max(a[i+1], sum[i] + a[i+1])
result = max(result, sum[i])
2.5 Further Thinking
- What if the input array is two-demensional?
- What if you need to find the largest product?
- How to find the start and end index of the subarray that meets the requirement?
3. Data Structures and Algorithm Analysis in C
Here we show 4 implementations in the book Data Structures and Algorithm Analysis in C.
// Algorithm 1: with time efficiency O(n*n*n)
int MaxSubsequenceSum1(const int A[], int N)
{
int ThisSum = 0 , MaxSum = 0, i, j, k;
for (i = 0; i < N; i++)
for (j = i; j < N; j++)
{
ThisSum = 0;
for (k = i; k < j; k++)
ThisSum += A[k];
if (ThisSum > MaxSum)
MaxSum = ThisSum;
}
return MaxSum;
}
//Algorithm 2: with time efficiency O(n*n)
int MaxSubsequenceSum2(const int A[], int N)
{
int ThisSum = 0, MaxSum = 0, i, j, k;
for (i = 0; i < N; i++)
{
ThisSum = 0;
for (j = i; j < N; j++)
{
ThisSum += A[j];
if (ThisSum > MaxSum)
MaxSum = ThisSum;
}
}
return MaxSum;
}
// Algorithm 3: with time efficiency O(n*log n)
// Main idea: using divide-and-conquer algorithm to
// devide the sequence into two parts, then the subarray
// with largest sum would appear in the following 3 cases:
// case 1: appears the left part
// case 2: appears in the right part
// case 3: appears between the two parts
// we discuss each case
static int MaxSubSum(const int A[], int Left, int Right)
{
// the subarray with largest sum on each side corresponding to case 1 and case 2
int MaxLeftSum, MaxRightSum;
// the subarray with largest sum across the middle from the left side or to the right side
// it corresponds to case 3
int MaxLeftBorderSum, MaxRightBorderSum;
int LeftBorderSum, RightBorderSum;
int Center, i;
if (Left == Right)Base Case
if (A[Left] > 0)
return A[Left];
else
return 0;
Center = (Left + Right) / 2;
MaxLeftSum = MaxSubSum(A, Left, Center);
MaxRightSum = MaxSubSum(A, Center + 1, Right);
MaxLeftBorderSum = 0;
LeftBorderSum = 0;
for (i = Center; i >= Left; i--)
{
LeftBorderSum += A[i];
if (LeftBorderSum > MaxLeftBorderSum)
MaxLeftBorderSum = LeftBorderSum;
}
MaxRightBorderSum = 0;
RightBorderSum = 0;
for (i = Center + 1; i <= Right; i++)
{
RightBorderSum += A[i];
if (RightBorderSum > MaxRightBorderSum)
MaxRightBorderSum = RightBorderSum;
}
int max1 = MaxLeftSum > MaxRightSum ? MaxLeftSum : MaxRightSum;
int max2 = MaxLeftBorderSum + MaxRightBorderSum;
return max1 > max2 ? max1 : max2;
}
// Algorithm 4: with time efficiency O(n)
// same as idea 3 and 4 from section 1.
int MaxSubsequenceSum(const int A[], int N)
{
int ThisSum, MaxSum, j;
ThisSum = MaxSum = 0;
for (j = 0; j < N; j++)
{
ThisSum += A[j];
if (ThisSum > MaxSum)
MaxSum = ThisSum;
else if (ThisSum < 0)
ThisSum = 0;
}
return MaxSum;
}
The original post can be found here.