Maximum subsequence and algorithm analysis

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

The problem is to find the maximum value of the sum of consecutive sub-series. If the maximum value is a negative number, take 0, such as the 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, and we can set the subsequence The left end i and the right end j, and then use a layer to calculate the sum from a[i] to a[j].

//Maximum sub-column 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 result*/
}
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 a rhythm that has to be calculated to death, we can clearly see the third level of for loop. Every time

j is added, the sum of the subcolumns has to 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 them. We divide the original sequence into one is two, then the largest subsequence is on the left, on the right, or across the boundary. The basic idea is as follows:

Step 1: 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 minute
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 Maximum sum of middle crossing border sequences*/
int NewLeft = 0,Max_BorderLeft=0, NewRight = 0,Max_BorderRight=0;
for (i = mid; i >= low; i--){ /*Scan left Find the maximum sum*/
NewLeft += a[i];
if (NewLeft > Max_BorderLeft)
Max_BorderLeft = NewLeft;
}
for (i = mid + 1; i <= high; i++){ /* towards Right scan to find the maximum subsequence sum */
NewRight+=a[i];
if (NewRight >= Max_BorderRight)
Max_BorderRight = NewRight;
}
MidSum = Max_BorderRight + Max_BorderLeft;
return Max(LeftSum, MidSum, RightSum) ; /*Return the result of the rule*/
}
int Max(int ​​a, int b, int c){ /*Find the largest number among the three*/
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 the maximum subsequence sum*/
if (NewSum < 0) /*Abandon it if it is less than 0*/
NewSum = 0;
}
return MaxSum;
}

This algorithm is to read the data one by one After scanning once, there is only one for loop. The algorithms for solving the same problem are very different. The trick lies in letting the computer remember some key intermediate results to avoid repeated calculations.

The above introduces the maximum subsequence and algorithm analysis, including aspects of the content. I hope it will be helpful to friends who are interested in PHP tutorials.