Question: A subarray has one number of some continuous numbers. Given an integer array with positive numbers and negative numbers, get the maximum sum of all subarrays. Time complexity should be O(n).
For example, in the array {1, 2, 3, 10, 4, 7, 2, 5}, its subarray {3, 10, 4, 7, 2} has the maximum sum 18.
Analysis: During interviews, many candidates can solve it by enumerating all of subarrays and calculate their sum. An array with n elements has n(n+1)/2 subarrays. It costs O(n^{2}) 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 subarrays. At the sixth step, we add the sixth number 7 and sum is 16. Now sum is greater than the previous max sum of subarrays, we need to update it to 16. It is same when we add the seventh number 2. The max sum of subarrays is updated to 18. Lastly we add 5 and sum becomes 13. Since it is less than the previous max sum of subarrays, it final max sum of subarray is 18, and the subarray is {3, 10, 4, 7, 2} accordingly. We can summarize the whole process with the Table 1:
Step

Operation

Accumulated sum of subarrays

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 subarrays 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 subarrays 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 sumarray 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 subarray ended with the (i1)^{th} number is negative, the sum of subarray 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 subarray ended with the i^{th} number by adding the i^{th} number and the sum of subarray 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.
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.
Should the condition in DP formula be
ReplyDeletei=0 or f(i1)<=0
i<>0 and f(i1)>0
Thanks for your reminding. Yes, there is a mistake in the equation. I'll revise it later.
DeleteThis comment has been removed by the author.
ReplyDeletecheck this for c# interview questions @ http://skillgun.com
ReplyDeleteif all array numbers are negative, it can be checked in advance and max array element should be returned in this case
ReplyDeleteif all array numbers are negative, it can be checked in advance and max array element should be returned in this case
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteI 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
ReplyDeleteYou 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