Maximum subsequence sum algorithm analysis, subsequence algorithm analysis

Maximum subsequence sum algorithm analysis, subsequence algorithm analysis_PHP tutorial

WBOY

Release： 2016-07-13 09:45:05

Original

816 people have browsed it

Maximum subsequence sum algorithm analysis, subsequence algorithm analysis

Problem description: Given n integer sequences {a1, a2,...,an}, find the function f (i,j)=max{0,Σa_k}(k: continuously taken from i to j);

The problem is to find the maximum value of the sum of consecutive sub-columns. If the maximum value is a negative number, take 0, such as an 8-number sequence {-1,2,-3,4,-2,5, -8,3}, the maximum subsequence sum of Namo is 4 (-2) 5=7.

This problem has four algorithms with different complexity. The time complexity of algorithms 1 to 4 is O(n³), O(n²), O(nlogn ),O(n);

Algorithm 1:

The most direct method is the exhaustive method. List all situations. We can set the left end i and right end j of the subsequence, and then use one layer to calculate the sum from a[i] to a[j].

//Maximum subcolumn and exhaustive method
#include
using namespace std;
int Find_Maxsun(int*a, int n);
int main(){
int n, i;
int a[100];
cin >> n;
cout << "Pleace Input The " << n << "Number :" << endl;
for (i = 0; i < n; i )
cin >> a[i];
cout< return 0;
}
int Find_Maxsun(int*a, int n){
int MaxSun = 0, i, j, k;
int NowSum;
for (i = 0; i < n; i ) /*left end of subsequence*/
for (j = 0; j < n; j ){ /*right end of subsequence*/
NowSum = 0;
for (k = i; k <= j; k )
NowSum = a[k]; /*Subsequence from a[i] to a[j]*/
if (NowSum>MaxSun)
MaxSun = NowSum; /*Update results*/
}
return MaxSun;
}

Obviously, the brute force method uses three for loops, and the algorithm time complexity is O(n³). This is of course the stupidest algorithm, but when the data is very large, even if it is To calculate the rhythm until death, we can clearly see the third layer of for loop,

Every time j is added, the sum of the subseries must be calculated again, so why don’t we use the result of j-1? That is to say, we save the result of j-1. When calculating the result of step j, we only need to add a[j] on the basis of step j-1, so there is Algorithm 2.

Algorithm 2:

#include
using namespace std;
int Find_Maxsun2(int*a, int n);
int main(){
int n, i;
int a [100];
cin >> n;
cout << "Pleace Input The " << n << " Number:" << endl;
for (i = 0; i < n; i )
cin >> a[i];
cout << Find_Maxsun2(a, n) << endl;
return 0 ;
}
int Find_Maxsun2(int*a, int n){
int i, j, NewSum = 0, MaxSum= 0;
for (i = 0; i < n; i ){ /* is the left endpoint of the sequence*/
NewSum = 0;
for (j = i; j < n; j ){ /*j is the right endpoint of the series*/
NewSum = a [j]; /*Update NewSum each time under j-1 condition*/
if (NewSum>MaxSum) /*Update MaxSum*/
MaxSum = NewSum;
}
}
return MaxSum;
}

This algorithm is smarter than 1, and the algorithm complexity is O(n²), which is obviously not the complexity we want.

Algorithm 3:

Algorithm 3 uses the idea of divide and conquer. The basic idea is self-evident: first divide and then conquer, decompose the problem into small problems and then sum up the small problems to solve. We divide the original sequence into two, then The largest subsequence is on the left, on the right, or across the boundary. The basic idea is as follows:

Step one: Divide the original sequence into two, into a left sequence and a right sequence.

Step 2: Recursively find the subsequences S left and S right.

Part 3: Scan from the center line to both sides to find the largest subsequence across the center line and S.

Step 4: Find S=max{S left, S middle, S right};

The code is implemented as follows:

#include
using namespace std;
int Find_MaxSum3(int*a,int low,int high);
int Max(int a,int b,int c);
int main(){
int n, i;
int a[100];
cin >> n;
cout << "Pleace Input The " << n << " Number:" << endl;
for (i = 0; i < n; i )
cin >> a[i];
cout < < Find_MaxSum3(a,0,n-1) << endl;
return 0;
}
int Find_MaxSum3(int*a,int low,int high){
int MaxSum = 0, MidSum, LeftSum, RightSum,i;
MidSum = 0;
if (low == high){ /*Termination condition of recursion*/
if (a[low] > 0)
return a[low];
else
return 0;
}
int mid = (low high) / 2; //Find the midpoint of the score
LeftSum = Find_MaxSum3( a, low, mid); /*Recursively find the maximum sum of the left sequence*/
RightSum = Find_MaxSum3(a, mid 1, high); /*Recursively find the maximum subsequence sum of the right sequence*/
/*Then You can find the maximum sum of the intermediate crossing-border sequences */
int NewLeft = 0,Max_BorderLeft=0, NewRight = 0,Max_BorderRight=0;
for (i = mid; i >= low; i--) { /*Scan left to find the maximum sum*/
NewLeft = a[i];
if (NewLeft > Max_BorderLeft)
Max_BorderLeft = NewLeft;
}
for (i = mid 1; i <= high; i ){ /*Scan right to find the largest subsequence and*/
NewRight =a[i];
if (NewRight >= Max_BorderRight)
Max_BorderRight = NewRight ;
}
MidSum = Max_BorderRight Max_BorderLeft;
return Max(LeftSum, MidSum, RightSum); /*Return the result of treatment*/
}
int Max(int a, int b, int c){ /*Find the largest number among the 3*/
if ( a>= b&&a >= c)
return a;
if (b >= a&&b >= c )
return b;
if (c >= b&&c>=a)
return c;
}

Let’s calculate the time complexity of this algorithm:

T(1)=1;

T(n)=2T(n/2) O(n);

=2^kT(n/2^k) kO(n)=2^kT(1) kO(n) (where n= 2^k)=n nlogn=O(nlogn);

Although this algorithm is very good, it is not the fastest algorithm.

Algorithm 4:

Algorithm 4 is called online processing. This means that every time a piece of data is read in, it is processed in time, and the result obtained is true for the currently read data, that is, the algorithm can give the correct solution at any position, and the algorithm can give the correct solution while reading.

#include
using namespace std;
int Find_MaxSum4(int*a, int n);
int main(){
int n, i;
int a [100];
cin >> n;
cout << "Pleace Input The " << n << " Number:" << endl;
for (i = 0; i < n; i )
cin >> a[i];
cout << Find_MaxSum4(a,n) << endl;
return 0 ;
}
int Find_MaxSum4(int*a, int n){
int i, NewSum = 0, MaxSum = 0;
for (i = 0; i < n; i ){
NewSum = a[i]; /*Current subsequence sum*/
if (MaxSum < NewSum)
MaxSum = NewSum; /*Update maximum subsequence sum*/
if (NewSum < 0) /*Discard if less than 0*/
NewSum = 0;
}
return MaxSum;
}

This algorithm scans the read data one by one, with only one for loop. The algorithms for solving the same problem are very different. The trick is to let the computer remember some key intermediate results to avoid repeated calculations.