Maximum Sum of All Subarrays (solve using dynamic programming)
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: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(this is a simple approach)
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.
No comments:
Post a Comment