No. 03 - Maximum Sum of All Sub-arrays

Question: A sub-array has one number of some continuous numbers. Given an integer array with positive numbers and negative numbers, get the maximum sum of all sub-arrays. Time complexity should be O(n).

For example, in the array {1, -2, 3, 10, -4, 7, 2, -5}, its sub-array {3, 10, -4, 7, 2} has the maximum sum 18.

Analysis: During interviews, many candidates can solve it by enumerating all of sub-arrays and calculate their sum. An array with n elements has n(n+1)/2 sub-arrays. It costs O(n²) time at least to calculate their sum. Usually the intuitive and forceful solution is not the most optimized one. Interviewers will tell us that there are better solutions.

Solution 1: Analyze arrays number by number

We try to accumulate every number in the example array from first to end. We initialize sum as 0. At our first step, add the first number 1, and sum is 1. And then if we add the second number -2, sum becomes -1. At the third step, we add the third number 3. We can notice that sum is less than 0, so the new sum will be 2 and it is less than the third number 3 itself if we add it with a negative sum. Therefore, the accumulated sum can be discarded.

We continue accumulating from the third number with sum 3. When we add it with the fourth number 10, sum becomes 13, and it decreases to 9 when we add it with the fifth number -4. We can notice that the sum with -4 is less than the previous sum since -4 is a negative number. Therefore, we should store the previous sum 13, since it might be the max sum of sub-arrays. At the sixth step, we add the sixth number 7 and sum is 16. Now sum is greater than the previous max sum of sub-arrays, we need to update it to 16. It is same when we add the seventh number 2. The max sum of sub-arrays is updated to 18. Lastly we add -5 and sum becomes 13. Since it is less than the previous max sum of sub-arrays, it final max sum of sub-array is 18, and the sub-array is {3, 10, -4, 7, 2} accordingly. We can summarize the whole process with the Table 1:

Step	Operation	Accumulated sum of sub-arrays	Maximum sum
1	Add 1	1	1
2	Add -2	-1	1
3	Discard previous sum -1, add 3	3	3
4	Add 10	13	13
5	Add -4	9	13
6	Add 7	16	16
7	Add 2	18	18
8	Add -5	13	18

Table 1: The process to calculate the maximum sum of all sub-arrays in the array {1, -2, 3, 10, -4, 7, 2, -5}

After we get clear ideas of this solution, we are ready to develop some code. The following is the sample code:

bool g_InvalidInput = false;

      

int FindGreatestSumOfSubArray(int *pData, int nLength)

{

    if((pData == NULL) || (nLength <= 0))

    {

        g_InvalidInput = true;

        return 0;

    }

    g_InvalidInput = false;

    int nCurSum = 0;

    int nGreatestSum = 0x80000000;

    for(int i = 0; i < nLength; ++i)

    {

        if(nCurSum <= 0)

            nCurSum = pData[i];

        else

            nCurSum += pData[i];

        if(nCurSum > nGreatestSum)

            nGreatestSum = nCurSum;

    }

    return nGreatestSum;

}

We should keep invalid inputs during interview, such as the pointer parameter of array is NULL or its length is 0. What should be return for the invalid inputs? If it is 0, how can we distinguish the two situations: one is for the actual maximum sum of sub-arrays is 0 and the other is for invalid inputs? Therefore, we define a global variable to make whether inputs are invalid or not.

Solution 2: Dynamic programming

If we have a deep understanding of algorithm, we may solve this problem with dynamic programming. If function f(i) stands for the maximum sum of a sum-array ended with the i^th number, what it is to get is max[f(i)]. We can calculate f(i) with the following recursive equation:

 

In the equation above, if the sum of sub-array ended with the (i-1)^th number is negative, the sum of sub-array ended with the i^th number should be the i^th number itself (it is the third step in the Table 1). Otherwise, we can get the sum of sub-array ended with the i^th number by adding the i^th number and the sum of sub-array ended with the previous number.

Even though we analyze the problem recursively, we will write code based on iteration eventually. The iterative code according to the equation above should be save to the code of the first solution. nCursum is the f(i) in the equation, and nGreatestSum is max[f(i)]. Therefore, these two solutions are essentially identical to each other.

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.