Find the solution to the maximum sum of subarrays in detail
- 2020-04-01 23:47:28
- OfStack
Enter an array of integers, both positive and negative. One or more consecutive integers in an array form a subarray, each of which has a sum. Find the maximum value of the sum of all subarrays. The time complexity is order n.
For example, the input array is 1, -2, 3, 10, -4, 7, 2, -5, and the largest subarray is 3, 10, -4, 7, and 2, so the output is the sum of that subarray, 18.
Without considering the time complexity, we can enumerate all the subarrays and find the sum of them. Unfortunately, because an array of length n has O(n2) subarrays; And the time complexity of finding the sum of an array of length n is order n. So this is order n3.
It's easy to understand that when we add a positive number, the sum increases; When we add a negative number, the sum decreases. If the current sum is negative, then the sum should be discarded and reset in the following sum, otherwise the negative sum will reduce the following sum. Based on this idea, we can write the following code:
Discussion: there are two points in the above code that are worth discussing with you:
The & # 8226; The return value of the function is not the maximum value of the subarray sum, but a marker to determine whether the input is valid. If the function returns the maximum value of the sum of subarrays, what should be returned when a null pointer is entered? Return 0? So how does the user of this function distinguish between an invalid input and a sum of subarrays whose maximum value happens to be 0? Based on this consideration, I believe that the maximum value of the subarray and is put into the parameter list by reference, while the function returns a sign that the function is performing properly.
The & # 8226; There is a special class of input cases that require special handling. When all integers in the input array are negative, the maximum value of the subarray sum is the largest element in the array.
Method 2: the beauty of programming
Another way of traversing from front to back is as follows:
Expansion question 1:
If you consider the array to be circular, that is, end to end (the subscript n-1 is followed by the subscript 0), find the largest subsegment sum.
Resolution:
I think this problem is easier than the first one. There are many ways to solve it. I introduce three methods, but one of them I think is a problem, but as an exercise in the beauty of programming, or maybe I misunderstood the author's algorithm, and I'll discuss it later.
Method one:
The optimal solution to this problem must be the following two possibilities. Possibility 1: the optimal solution does not span a[n-1] to a[0], that is, the original problem, non-circular array. Possibility two: the optimal solution crosses a[n-1] to a[0]. New problem.
For the first case, we can follow the simple dynamic programming solution, set as max1; In the second case, you can turn the original problem into the smallest segment sum of the array, and then subtract the smallest segment sum from the sum of all the elements of the array. The result must be the largest subsegment sum from a[n-1] to a[0], set to max2. The end result is the larger of the max1 and max2.
Example 1: there are arrays 6, -1, -6, 8, 2
Get max1=10, max2=16, then take the larger max2 as the result.
Example 2: there are arrays -6, 8, 2, 6, -1
Get max1=16, max2=15, then take the larger max1 as the result.
Some of you may wonder why: the array element sum - smallest child sum = spans the largest child sum from a[n-1] to a[0]. We can think of it this way: the sum of n Numbers is a certain number, so if we find a continuous number in the n Numbers, and this number is the smallest sum of all consecutive Numbers, then the result of "sum- smallest sum" must be the largest. Therefore, it can be obtained that: the sum of the largest subsegments from a[n-1] to a[0].
The complete code is as follows:
In the first part, the maximum value of the first case is Max 1 (replaced by the variable Max). In the second part, the initial TMP is the smallest segment sum, and then the TMP value is sum-tmp. And then Max takes the larger of the two.
Method 2:
Method 2 turns the problem into another problem: since the heads and tails of a number can be connected, we can copy the array and attach it to our own, and then we can find the sum of the largest subarray of the new array, but we have to limit the length of the largest subarray to no more than n. So we can turn the problem into expansion problem 3, which I'll cover in part 3.
Method 3:
Method 3 is introduced in the book "the beauty of programming", see page 188 for details, but I think this algorithm is wrong, may be I understand the author's ideas have problems, I will copy the solution in the following, and give a counter example, interested students hope to give me a message.
From the beauty of programming P188:
If the array (A[0],A[1],A[2],... A[n-1]), which means we are allowed to find A number (A[I],A[I +1]... A [n - 1], A [0], A [1],... A[j]) to maximize the sum.
(1) the solution does not cross A[n-1] to A[0] (original problem).
(2) the solution crosses A[n-1] to A[0].
For the second case, just find the segment (A[0],... [j]), A (0 < = j < N), and the largest paragraph ending in A[n-1] (A[I]... ], A [n - 1) (0 < = I < N), then, in the second case, the maximum value M_2 of and is:
M_2 = A [I] +... + A + A/n - 1] [0] +... + A [j].
If I < = j,
M_2 = A [0] +... + A/n - 1)
Otherwise,
M_2 = A [0] +... [I] [j] + A + A +... + A/n - 1)
Finally, it is ok to take the maximum value of the two cases again. For the case of crossing A[n-1] to A[0], it only needs to go through the groups once, so the total time complexity is O(n)+O(n)=O(n).
Resolution:
It is no problem to divide the discussion into two cases, but I think the solution of the second case is wrong. Counter example:
Find the largest subarray of an array of 5 elements, 6,-1,-6,8, and 2: M_1 is 10, but if you use the above method, M_2 is 9, because A[0] starts at A[0] and the largest segment is A[0]... A[n-1] = 9 the largest sum ending in A[n-1] (A[I]... ,A[n-1]) is A[n-1], since the two segments have intersection, M_2= A[0]+... + A/n - 1).
The final result is 9. If you take the larger of the two cases, the final result is 10. But the correct result is obviously 16.
The reason for this result: starting from A[0] and the largest segment, although there is nothing wrong, we hope to get the result is not this segment, we hope to get A[0] segment, so that the two segments will not intersect.
In the second part, I analyzed two expansion problems, and I will analyze the following two expansion problems in the third part.
If there is something wrong with my writing or if you have a better way, I hope you can come up with it and learn from each other.
Expansion question 2:
There is a sequence of integers, in which there are negative Numbers, positive Numbers, in which several consecutive Numbers sum, sum of the absolute value of the largest number string.
Analysis of the
Train of thought
The sum of the largest submatrices
For example, the input array is 1, -2, 3, 10, -4, 7, 2, -5, and the largest subarray is 3, 10, -4, 7, and 2, so the output is the sum of that subarray, 18.
Without considering the time complexity, we can enumerate all the subarrays and find the sum of them. Unfortunately, because an array of length n has O(n2) subarrays; And the time complexity of finding the sum of an array of length n is order n. So this is order n3.
It's easy to understand that when we add a positive number, the sum increases; When we add a negative number, the sum decreases. If the current sum is negative, then the sum should be discarded and reset in the following sum, otherwise the negative sum will reduce the following sum. Based on this idea, we can write the following code:
/*
// Find the greatest sum of all sub-arrays
// Return value: if the input is valid, return true, otherwise return false
int *pData, // an array
unsigned int nLength, // the length of array
int &nGreatestSum // the greatest sum of all sub-arrays
*/
int start,end;
bool FindGreatestSumOfSubArray(int *pData, unsigned int nLength, int &nGreatestSum)
{
// if the input is invalid, return false
if((pData == NULL) || (nLength == 0))
return false;
int k=0;
int nCurSum = nGreatestSum = 0;
for(unsigned int i = 0; i < nLength; ++i)
{
nCurSum += pData[i];
// if the current sum is negative, discard it
if(nCurSum < 0)
{
nCurSum = 0;
k = i+1;
}
// if a greater sum is found, update the greatest sum
if(nCurSum > nGreatestSum)
{
nGreatestSum = nCurSum;
start = k;
end = i;
}
}
// if all data are negative, find the greatest element in the array
if(nGreatestSum == 0)
{
nGreatestSum = pData[0];
for(unsigned int i = 1; i < nLength; ++i)
{
if(pData[i] > nGreatestSum)
{
nGreatestSum = pData[i];
start = end = i;
}
}
}
return true;
}
Discussion: there are two points in the above code that are worth discussing with you:
The & # 8226; The return value of the function is not the maximum value of the subarray sum, but a marker to determine whether the input is valid. If the function returns the maximum value of the sum of subarrays, what should be returned when a null pointer is entered? Return 0? So how does the user of this function distinguish between an invalid input and a sum of subarrays whose maximum value happens to be 0? Based on this consideration, I believe that the maximum value of the subarray and is put into the parameter list by reference, while the function returns a sign that the function is performing properly.
The & # 8226; There is a special class of input cases that require special handling. When all integers in the input array are negative, the maximum value of the subarray sum is the largest element in the array.
Method 2: the beauty of programming
int maxSum(int *arr, int n, int & start, int & end)
{
int i , temp , dp , max ;
dp = max = arr[n-1];
start = end = n-1;
temp = n-1;
for(i = n - 2 ; i >= 0 ; --i)
{
if(dp > 0)
dp += arr[i];
else
{
dp = arr[i]; //Discard the current subsequence
temp = i; //Start a new subsequence search
}
if(dp > max) //Updates the largest subsequence
{
max = dp;
end = temp;
start = i; //The maximum and the increase, the I must be at the right end
}
}
return max;
}
//Special test case -10 -1 -4
Another way of traversing from front to back is as follows:
//When you need to save the start and end subscripts, it is also possible to traverse from front to back
int MaxSum(int *a , int n)
{
int tempstart = 0 , sum=0 , max = -1000;
int i , start , end;
start = end = 0;
for(i = 0 ; i < n ; ++i)
{
if(sum < 0)
{
sum = a[i];
tempstart = i;
}
else
sum += a[i];
if(sum > max)
{
max = sum;
start = tempstart;
end = i;
}
}
return max;
}
Expansion question 1:
If you consider the array to be circular, that is, end to end (the subscript n-1 is followed by the subscript 0), find the largest subsegment sum.
Resolution:
I think this problem is easier than the first one. There are many ways to solve it. I introduce three methods, but one of them I think is a problem, but as an exercise in the beauty of programming, or maybe I misunderstood the author's algorithm, and I'll discuss it later.
Method one:
The optimal solution to this problem must be the following two possibilities. Possibility 1: the optimal solution does not span a[n-1] to a[0], that is, the original problem, non-circular array. Possibility two: the optimal solution crosses a[n-1] to a[0]. New problem.
For the first case, we can follow the simple dynamic programming solution, set as max1; In the second case, you can turn the original problem into the smallest segment sum of the array, and then subtract the smallest segment sum from the sum of all the elements of the array. The result must be the largest subsegment sum from a[n-1] to a[0], set to max2. The end result is the larger of the max1 and max2.
Example 1: there are arrays 6, -1, -6, 8, 2
Get max1=10, max2=16, then take the larger max2 as the result.
Example 2: there are arrays -6, 8, 2, 6, -1
Get max1=16, max2=15, then take the larger max1 as the result.
Some of you may wonder why: the array element sum - smallest child sum = spans the largest child sum from a[n-1] to a[0]. We can think of it this way: the sum of n Numbers is a certain number, so if we find a continuous number in the n Numbers, and this number is the smallest sum of all consecutive Numbers, then the result of "sum- smallest sum" must be the largest. Therefore, it can be obtained that: the sum of the largest subsegments from a[n-1] to a[0].
The complete code is as follows:
//A ring array takes the sum of the largest subarray
int MaxSum(int *a , int n)
{
int i , sum , max1 , max2 , dp, min;
dp = max1 = a[0];
for(i = 1 ; i < n ; ++i) //The optimal solution does not go from a[n-1] to a[0], which is the original problem, non-circular array
{
if(dp < 0)
dp = a[i];
else
dp += a[i];
if(dp > max1)
max1 = dp;
}
sum = min = dp = a[0];
for(i = 1 ; i < n ; ++i) //You can turn the original problem into the smallest segment sum of the array, and then subtract the smallest segment sum from the sum of all the elements of the array, and the result must be the largest subsegment sum from a[n-1] to a[0]
{
if(dp > 0)
dp = a[i];
else
dp += a[i];
if(dp < min)
min = dp;
sum += a[i];
}
max2 = sum - min; //The sum of all the elements of the array minus the smallest sum
return max1 > max2 ? max1 : max2;; //Returns a larger value
}
In the first part, the maximum value of the first case is Max 1 (replaced by the variable Max). In the second part, the initial TMP is the smallest segment sum, and then the TMP value is sum-tmp. And then Max takes the larger of the two.
Method 2:
Method 2 turns the problem into another problem: since the heads and tails of a number can be connected, we can copy the array and attach it to our own, and then we can find the sum of the largest subarray of the new array, but we have to limit the length of the largest subarray to no more than n. So we can turn the problem into expansion problem 3, which I'll cover in part 3.
Method 3:
Method 3 is introduced in the book "the beauty of programming", see page 188 for details, but I think this algorithm is wrong, may be I understand the author's ideas have problems, I will copy the solution in the following, and give a counter example, interested students hope to give me a message.
From the beauty of programming P188:
If the array (A[0],A[1],A[2],... A[n-1]), which means we are allowed to find A number (A[I],A[I +1]... A [n - 1], A [0], A [1],... A[j]) to maximize the sum.
(1) the solution does not cross A[n-1] to A[0] (original problem).
(2) the solution crosses A[n-1] to A[0].
For the second case, just find the segment (A[0],... [j]), A (0 < = j < N), and the largest paragraph ending in A[n-1] (A[I]... ], A [n - 1) (0 < = I < N), then, in the second case, the maximum value M_2 of and is:
M_2 = A [I] +... + A + A/n - 1] [0] +... + A [j].
If I < = j,
M_2 = A [0] +... + A/n - 1)
Otherwise,
M_2 = A [0] +... [I] [j] + A + A +... + A/n - 1)
Finally, it is ok to take the maximum value of the two cases again. For the case of crossing A[n-1] to A[0], it only needs to go through the groups once, so the total time complexity is O(n)+O(n)=O(n).
Resolution:
It is no problem to divide the discussion into two cases, but I think the solution of the second case is wrong. Counter example:
Find the largest subarray of an array of 5 elements, 6,-1,-6,8, and 2: M_1 is 10, but if you use the above method, M_2 is 9, because A[0] starts at A[0] and the largest segment is A[0]... A[n-1] = 9 the largest sum ending in A[n-1] (A[I]... ,A[n-1]) is A[n-1], since the two segments have intersection, M_2= A[0]+... + A/n - 1).
The final result is 9. If you take the larger of the two cases, the final result is 10. But the correct result is obviously 16.
The reason for this result: starting from A[0] and the largest segment, although there is nothing wrong, we hope to get the result is not this segment, we hope to get A[0] segment, so that the two segments will not intersect.
In the second part, I analyzed two expansion problems, and I will analyze the following two expansion problems in the third part.
If there is something wrong with my writing or if you have a better way, I hope you can come up with it and learn from each other.
Expansion question 2:
There is a sequence of integers, in which there are negative Numbers, positive Numbers, in which several consecutive Numbers sum, sum of the absolute value of the largest number string.
Analysis of the
Train of thought
The sum of the largest submatrices
#include <iostream>
#include <cstdio>
using namespace std;
#include <memory.h>
int a[102][102];
int maxSubArray(int *arr, int len) //Maximum subsequence sum
{
int i,sum=arr[0],b=0;
for(i=0;i<len;++i)
{
if(b>0)
b+=arr[i];
else
b=arr[i];
if(b>sum)
sum=b;
}
return sum;
}
int maxSubMatrix(int n, int m,int array[102][102])
{
int i,j,h,max,sum=-100000;
int b[102];
for(i=0;i<n;i++)
{
memset(b,0,sizeof(b)); //Initialize the [b]
for(j=i;j<n;j++) //Add the ith row to the JTH row, and find the maximum value for each addition
{
for(h=0;h<m;h++)
{
b[h]+=array[j][h]; // A two-dimensional array is compressed into a one-dimensional array, and then we solve Maximum subsequence sum
}
max=maxSubArray(b,h);
if(max>sum)
sum=max;
}
}
return sum;
}
int main(void)
{
int n,i,j;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
}
printf("%dn",maxSubMatrix(n,n,a));
}
return 0;
}