Maximum subsequence and linear algorithm
Problem Description:
The given integer A1, A2, ... AN (possibly negative), find the maximum of I to J.
E.g:
-2, 11, -4, 13, -5, -2 answer is 20
There are many algorithms for this problem. Of course, I am going to use the "Dynamic Planning" algorithm implemented program. For this algorithm, I can say that many people have thought of, but they didn't want it (because I am like this). There is also a very classic solution for the dynamic planning of this problem, her time complexity is O (n), which is linear. And for the exhaustive method of its time complexity but O (N
3), this seems to be greatly improved.
Considering such a problem, we start with the simplest left, as the example above, is -2 has an impact on the results? No answer is. So let us look at the following example:
6, -7, ...
At this point, we need to consider 6 and -7, some people say, because maybe for 6, there is no bigger than it, yes. The problem is like this. So what is the effect on the following results? At this time we can say that there is no impact!
In the present, is it going to think about it? Oh, I once thought, then why don't we put this problem, down? The dynamic planning method is to solve such a problem, we know that the two numbers in the previous is an optimal sub-structure (although only 2 numbers are only fully promoted.)
The algorithm in the book tells us how to promote, the specific purpose of the article I wrote is to explain the above problems, because I have thought of the previous algorithm, but I didn't think about it. With this! And regret!
Then the algorithm in the book is like this: (See the "granted method" of this problem before this algorithm, so that you feel more than this algorithm.)
Int MaxSubsequencesum (const Int a [], int N)
{
Int Thissum, MaxSum, J;
Thissum = maxsum = 0;
For (j = 0; j { Thissum = a [j]; IF (thissum> maxsum) Maxsum = thissum; Else IF (Thissum <0) THISSUM = 0; } Return MaxSum; } Analysis of this algorithm (logic): Add from the right to the right, if the result is constantly increasing, then Thissum will increase with MaxSum. If you encounter a negative number, then it is added to Thissum, but this at this time thissum postscript:
