Thursday, September 15, 2011

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(n2) 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 ith 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 ith number should be the ith number itself (it is the third step in the Table 1). Otherwise, we can get the sum of sub-array ended with the ith number by adding the ith 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. 

9 comments:

  1. Should the condition in DP formula be
    i=0 or f(i-1)<=0
    i<>0 and f(i-1)>0

    ReplyDelete
    Replies
    1. Thanks for your reminding. Yes, there is a mistake in the equation. I'll revise it later.

      Delete
  2. This comment has been removed by the author.

    ReplyDelete
  3. if all array numbers are negative, it can be checked in advance and max array element should be returned in this case

    ReplyDelete
  4. if all array numbers are negative, it can be checked in advance and max array element should be returned in this case

    ReplyDelete
  5. This comment has been removed by the author.

    ReplyDelete
  6. I have a doubt regarding what if all numbers are negative, then the code will return the last negative no? Like what if its like {-1, -6, -5, -2} if it returns last no then solutions is not correct. Plz clarify

    ReplyDelete
    Replies
    1. You can simply let the nCurSum and nGreatestSum to be the first element of the array, in that way the greatest negative number will be the maximum sum which is indeed correct.

      Delete