The following is a subject description:
01 - complexity 2 Maximum Subsequence Sum (25 points)
Given a sequence of integers {K N
? 1
?? , N
? 2
?? . , N
? K
?? }. A continuous subsequence is defined to be {N
? I
?? , N
? I + 1
?? . , N
? J
?? 1} where I j K or less or less or less The Maximum Subsequence is The continuous Subsequence which has The largest sum of its elements, For example, given The sequence {2, 11, 4, 13, 5, 2}, and its Maximum Subsequence is 13} {11 to 4, with The largest sum being 20.
Now you are supposed to find the largest sum, together with the first and the last Numbers of the maximum subsequence.
Input Specification:
Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (10000) or less. The second line contains The K Numbers, separated by a space.
The Output Specification:
For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.
The Sample Input:
10
- 10 1 2 3 4-5-23 March 7 to 21
The Sample Output:
10 1 4



Online algorithm:
The following is the source code:
# include
# define MAX 100000
using namespace std;
Int func (int a [], int n, int & amp; Start, int & amp; End)
{
Int j=0, count=0;
Int flag=1;
Int TheSum=0, MaxSum=1;
for(int i=0; i{
TheSum +=a, [I].
If (a [I] <0) count++;
If (TheSum> MaxSum)
{
If (flag)
{
start=i;
Flag=0;
}
End=I;
MaxSum=TheSum;
}
Else if (TheSum<0)
{
TheSum=0;
Flag=1;
}
}
If (count==n) return 1;
Return MaxSum;
}
Int main ()
{
Int n=0, Max=0;
Int start=0, end=0;
Int a [MAX]={0};
Cin> n;
for(int i=0; I & lt; n; I++)
{
Cin> A, [I].
}
Max=func (a, n, start, end);
If (max<0)
Cout<& lt;" 0 "& lt; & lt;" "The else
Coutreturn 0;
}

Can not pass the test point description: coordinate and corresponding to the same but different j I, that is, the tail is 0 answers wrong
If this is not made up of two same size of the architectural sequence, take the subscript to the youngest, I recorded in the start and end of treatment, test a few number is correct, obtained is the smallest values, but the test point is, however, ask bosses give directions!!!!!

CodePudding user response:

9
1 5 0-9 2 4 0-9 0
6 1 5
May be this sequence is not approved?

CodePudding user response:

Through the error, also cry

CodePudding user response:

Reference:

 # include 
# define MAX 100000 

using namespace std; 

Int func (int a [], int n, int & amp; Start, int & amp; End) 
{
Int flag=0; 
Int TheSum=0, MaxSum=1; 
for(int i=0; i{
TheSum +=a, [I]. 
If (TheSum> MaxSum) 
{
Start=flag; 
End=I;//the architectural segment and the most the right side the subscript 
MaxSum=TheSum; 
} 
Else if (TheSum<0) 
{
TheSum=0; 
Flag=I + 1;//the architectural segment and the most left side subscript 
} 
} 
Return MaxSum; 
} 

Int main () 
{
Int n=0, Max=0; 
Int start=0, end=0; 
Int a [MAX]={0}; 
Cin> n; 
for(int i=0; I & lt; n; I++) 
{
Cin> A, [I]. 
} 
Max=func (a, n, start, end); 
If (max<0) 
Cout<& lt;" 0 "& lt; & lt;" "The else 
Cout
return 0; 
}