Is a bug? About MaxSubsequenceSum()

[xianwei]

int
MaxSubsequenceSum( const int A[], int N )
{
int ThisSum, MaxSum, j;

ThisSum = MaxSum = 0;
for (j = 0; j < N; j++)
{
ThisSum += A[j];

if (ThisSum > MaxSum)
{
MaxSum = ThisSum;
}
else if (ThisSum < 0)
{
ThisSum = 0;
}
}

return MaxSum;
}

I think the above code is a good choice to obtain MaxSubsequenceSum
T(n) = O(n), but If the array A contain full negative value, the
function will return zero.
I think to add a part code to test the A array value, but this will
destroy code grace, and then the code will become ugly(I think).
Do you have a good method to resolve the problem?

Thank you.

 

[Army1987]

int
MaxSubsequenceSum( const int A[], int N )
{
int ThisSum, MaxSum, j;

ThisSum = MaxSum = 0;
for (j = 0; j < N; j++)
{
ThisSum += A[j];

if (ThisSum > MaxSum)
{
MaxSum = ThisSum;
}
else if (ThisSum < 0)
{
ThisSum = 0;
}
}

return MaxSum;
}

I think the above code is a good choice to obtain MaxSubsequenceSum
T(n) = O(n), but If the array A contain full negative value, the
function will return zero.
I think to add a part code to test the A array value, but this will
destroy code grace, and then the code will become ugly(I think).
Do you have a good method to resolve the problem?

Initialize MaxSum and ThisSum to a[0], make the loop start with
j=1, and remove the else branch.
BTW, usually all-caps identifiers are used for macros, using
lowercase could be less confusing for people used to this
convention.

 

[Ben Bacarisse]

int
MaxSubsequenceSum( const int A[], int N )
{
int ThisSum, MaxSum, j;
ThisSum = MaxSum = 0;
for (j = 0; j < N; j++)
{
ThisSum += A[j];
if (ThisSum > MaxSum)
{
MaxSum = ThisSum;
}
else if (ThisSum < 0)
{
ThisSum = 0;
}
}
return MaxSum;
}

I think the above code is a good choice to obtain MaxSubsequenceSum
T(n) = O(n), but If the array A contain full negative value, the
function will return zero.
I think to add a part code to test the A array value, but this will
destroy code grace, and then the code will become ugly(I think).
Do you have a good method to resolve the problem?

Initialize MaxSum and ThisSum to a[0], make the loop start with
j=1, and remove the else branch.

I think that breaks it.

 

[Ben Bacarisse]

int
MaxSubsequenceSum( const int A[], int N )
{
int ThisSum, MaxSum, j;
ThisSum = MaxSum = 0;
for (j = 0; j < N; j++)
{
ThisSum += A[j];
if (ThisSum > MaxSum)
{
MaxSum = ThisSum;
}
else if (ThisSum < 0)
{
ThisSum = 0;
}
}
return MaxSum;
}

I think the above code is a good choice to obtain MaxSubsequenceSum
T(n) = O(n), but If the array A contain full negative value, the
function will return zero.
I think to add a part code to test the A array value, but this will
destroy code grace, and then the code will become ugly(I think).
Do you have a good method to resolve the problem?

Initialize MaxSum and ThisSum to a[0], make the loop start with
j=1, and remove the else branch.

I think that breaks it.

.... but thinking about it, if you meant setting MaxSum to a[0] and
ThisSum to 0, you may be right. It looks like that does what the OP
wants. Beware because, Unlike Knuth, I have only tested this, not
proved it!

 

[Mark Bluemel]

... It looks like that does what the OP wants.

I'm impressed you could work out what he wanted... It was pretty opaque
to me, but that may indicate my limitations...

 

[Ben Bacarisse]

I'm impressed you could work out what he wanted... It was pretty
opaque to me

I thought so too but the code is the standard way to find a maximal
*positive* sum, and Army1987's change seemed to be aiming to return
the maximum when the array has no elements >= 0. This is the
extension to the problem you get by removing the word "positive" --
return the maximal sub-sequence sum even if it is negative. All of a
sudden the mysterious phase "full negative" had a probable meaning.

Thus all the comprehension work was done by Army1987. I just inferred
the meaning from his code.

 

[Thad Smith]

int
MaxSubsequenceSum( const int A[], int N )
{ ....
}

I think the above code is a good choice to obtain MaxSubsequenceSum
T(n) = O(n), but If the array A contain full negative value, the
function will return zero.

And that would be correct. The subsequence with a run of 0 values has a
sum of 0.

 

[xianwei]

I thought so too but the code is the standard way to find a maximal
*positive* sum, and Army1987's change seemed to be aiming to return
the maximum when the array has no elements >= 0. This is the
extension to the problem you get by removing the word "positive" --
return the maximal sub-sequence sum even if it is negative. All of a
sudden the mysterious phase "full negative" had a probable meaning.

Oh, I'm sorry, My English is so poor~~

"full negative" means no positive value in Array A[], and the
MaxSubsequenceSun() will return zero, But I think the value is
wrong.~~~

 

[Army1987]

I thought so too but the code is the standard way to find a maximal
*positive* sum, and Army1987's change seemed to be aiming to return
the maximum when the array has no elements >= 0. This is the
extension to the problem you get by removing the word "positive" --
return the maximal sub-sequence sum even if it is negative. All of a
sudden the mysterious phase "full negative" had a probable meaning.

(my code:
int
MaxSubsequenceSum( const int A[], int N )
{
int ThisSum, MaxSum, j;

ThisSum = MaxSum = a[0];
for (j = 1; j < N; j++)
{
ThisSum += A[j];

if (ThisSum > MaxSum)
{
MaxSum = ThisSum;
}
}
return MaxSum;
}

Thus all the comprehension work was done by Army1987. I just inferred
the meaning from his code.

Well, what I've done should find the *initial* subsequence with
the greatest possible sum... (Note that I just realized that the
if (ThisSum ...) part is only needed when a[j] is positive, but
checking this would only help if comparisons with 0 are faster,
because in both cases one comparison would be done.)

OK, until the OP explains more clearly what he wanted, let's stop
guessing.

 

[xianwei]

(my code:
int
MaxSubsequenceSum( const int A[], int N )
{
int ThisSum, MaxSum, j;

ThisSum = MaxSum = a[0];
for (j = 1; j < N; j++)
{
ThisSum += A[j];

if (ThisSum > MaxSum)
{
MaxSum = ThisSum;
}
}
return MaxSum;

}

I think you misunderstanding what I said.~~~~~,or I don't express
clearly.
MaxSubsequenceSum means like below:

A[] = { -10, -7, 10, 7, 3, -3, 5, -3 };

the function will return 10 + 7 + 3 -3 + 5 ~~~~, But I think you
program
can't do this, But thank you enthusiasm, ~~~

 

[Ben Bacarisse]

Oh, I'm sorry, My English is so poor~~

"full negative" means no positive value in Array A[], and the
MaxSubsequenceSun() will return zero, But I think the value is
wrong.~~~

Why do you think it is wrong? The convention is (and it is only a
convention) that when there are no positive elements the maximal
sub-sequence sum should be zero. If all the A are negative, you
get the largest sum by adding none of them. A common definition for
the sum of no elements is 0.

There is a reasonable alternative meaning: that when all the A are
negative you return the largest (least negative) value but there is no
reason, without more context, to suppose that this is what is wanted.

So you need to say why think returning 0 is the wrong thing to do, and
then you need to say what you want the program to do in the case where
all the elements are <0. But if this is plain "homework" your
solution looks correct to me.

 

[Ben Bacarisse]

I thought so too but the code is the standard way to find a maximal
*positive* sum, and Army1987's change seemed to be aiming to return
the maximum when the array has no elements >= 0. This is the
extension to the problem you get by removing the word "positive" --
return the maximal sub-sequence sum even if it is negative. All of a
sudden the mysterious phase "full negative" had a probable meaning.

(my code:
int
MaxSubsequenceSum( const int A[], int N )
{
int ThisSum, MaxSum, j;>

ThisSum = MaxSum = a[0];
for (j = 1; j < N; j++)
{
ThisSum += A[j];

if (ThisSum > MaxSum)
{
MaxSum = ThisSum;
}
}
return MaxSum;
}

Thus all the comprehension work was done by Army1987. I just inferred
the meaning from his code.

Well, what I've done should find the *initial* subsequence with
the greatest possible sum... (Note that I just realized that the
if (ThisSum ...) part is only needed when a[j] is positive, but
checking this would only help if comparisons with 0 are faster,
because in both cases one comparison would be done.)

Oh, the irony! I understood the OP's intent and misunderstood yours!
I *think* the following (which is a correction of what I *thought* you
meant)

int
MaxSubsequenceSum( const int A[], int N )
{
int ThisSum, MaxSum, j;
ThisSum = 0;
MaxSum = A[0];
for (j = 1; j < N; j++)
{
ThisSum += A[j];
if (ThisSum > MaxSum)
MaxSum = ThisSum;
if (ThisSum < 0)
ThisSum = 0;
}
return MaxSum;
}

Implements the "other" common meaning for the maximal sub-sequence sum
where empty sub-sequences are not allowed (thus returning the maximum
element when all the A are negative). However, as I said, this is
unproved and at best unusual. As stated elsewhere, I think what OP
posted is what is usually done.

OK, until the OP explains more clearly what he wanted, let's stop
guessing.

You are right, but I could not help explaining what I thought you had
intended.

 

[Army1987]

I think you misunderstanding what I said.~~~~~,or I don't express
clearly.
MaxSubsequenceSum means like below:

A[] = { -10, -7, 10, 7, 3, -3, 5, -3 };

the function will return 10 + 7 + 3 -3 + 5 ~~~~, But I think you
program
can't do this, But thank you enthusiasm, ~~~

So your original program is correct. If all the members of A are
negative the subsequence with the largest sum is the empty
subsequence.

 

[Army1987]

Why do you think it is wrong? The convention is (and it is only a
convention) that when there are no positive elements the maximal
sub-sequence sum should be zero. If all the A are negative, you
get the largest sum by adding none of them. A common definition for
the sum of no elements is 0.

<ot>
Another example where disallowing empty sets makes the solution
harder. I saw a puzzle on a Web forum asking whether there is a
real-valued function in one real variable, which maps every open
interval to R. I answered that there is no such function, as the
empty set is open, e.g. (0, 0), and its image cannot be nonempty.
Then I was told that I hadn't read the hypotheses, and I realized
that they read "any *nonempty* open interval".
</ot>

 

[xianwei]

Ben Bacarisse wrote:
... It looks like that does what the OP wants.
I'm impressed you could work out what he wanted... It was pretty
opaque to me
I thought so too but the code is the standard way to find a maximal
*positive* sum, and Army1987's change seemed to be aiming to return
the maximum when the array has no elements >= 0. This is the
extension to the problem you get by removing the word "positive" --
return the maximal sub-sequence sum even if it is negative. All of a
sudden the mysterious phase "full negative" had a probable meaning.

(my code:
int
MaxSubsequenceSum( const int A[], int N )
{
int ThisSum, MaxSum, j;>
ThisSum = MaxSum = a[0];
for (j = 1; j < N; j++)
{
ThisSum += A[j];

if (ThisSum > MaxSum)
{
MaxSum = ThisSum;
}
}
return MaxSum;
}

Thus all the comprehension work was done by Army1987. I just inferred
the meaning from his code.

Well, what I've done should find the *initial* subsequence with
the greatest possible sum... (Note that I just realized that the
if (ThisSum ...) part is only needed when a[j] is positive, but
checking this would only help if comparisons with 0 are faster,
because in both cases one comparison would be done.)

Oh, the irony! I understood the OP's intent and misunderstood yours!
I *think* the following (which is a correction of what I *thought* you
meant)

int
MaxSubsequenceSum( const int A[], int N )
{
int ThisSum, MaxSum, j;
ThisSum = 0;
MaxSum = A[0];
for (j = 1; j < N; j++)
{
ThisSum += A[j];
if (ThisSum > MaxSum)
MaxSum = ThisSum;
if (ThisSum < 0)
ThisSum = 0;
}
return MaxSum;

}

Thanks, you methods too beautiful.
I need more time to test, thanks.

 

[xianwei]

Oh, the irony! I understood the OP's intent and misunderstood yours!
I *think* the following (which is a correction of what I *thought* you
meant)

int
MaxSubsequenceSum( const int A[], int N )
{
int ThisSum, MaxSum, j;
ThisSum = 0;

ThisSum = A[0];

MaxSum = A[0];
for (j = 1; j < N; j++)
{
ThisSum += A[j];
if (ThisSum > MaxSum)
MaxSum = ThisSum;
if (ThisSum < 0)
ThisSum = 0;
}
return MaxSum;

}

If follow you way, the A[2] = { 5, 10 };
The function will return 10.~~~~
The Array first and second element > 0, and the last return value
can't
add the first positive value.~~~.
Thank you program.

 

[Ben Bacarisse]

Oh, the irony! I understood the OP's intent and misunderstood yours!
I *think* the following (which is a correction of what I *thought* you
meant)

int
MaxSubsequenceSum( const int A[], int N )
{
int ThisSum, MaxSum, j;
ThisSum = 0;

ThisSum = A[0];

MaxSum = A[0];
for (j = 1; j < N; j++)
{
ThisSum += A[j];
if (ThisSum > MaxSum)
MaxSum = ThisSum;
if (ThisSum < 0)
ThisSum = 0;
}
return MaxSum;

}

If follow you way, the A[2] = { 5, 10 };
The function will return 10.~~~~

Indeed. I had to go see what it was I was testing because my test
program worked! I was running the loop from 0 which, I think, also
works. Sorry, I somehow posted an edited version of the program.

Thank you program.

Please, before considering it correct, think through the argument that
your original is *better*. If it were my coursework, I would submit
your version, because I think the maximal sub-sequence sum is zero
when all the elements are negative. You might be asked to explain why
you think it should not be!

 

[xianwei]

Indeed. I had to go see what it was I was testing because my test
program worked! I was running the loop from 0 which, I think, also
works. Sorry, I somehow posted an edited version of the program.

Change
ThisSum = 0;
to
ThisSum = A[0];
will avoid the bug. But I don't know this way whether will leading a
new bug in code.

If it were my coursework, I would submit
your version, because I think the maximal sub-sequence sum is zero
when all the elements are negative. You might be asked to explain why
you think it should not be!

Yes, you may be right, "Max" sub-sequence certain contain zero
element.So When all the elements are negative, "Max" equal to "zero",
But I think "Max" at least contain one elements.So.....

Thanks you try to express you meaning clearly to me,~~,my English is
so poor, luckily, at end I understand what do you want present.

I think I should enhance My English skills.

 

[xianwei]

Indeed. I had to go see what it was I was testing because my test
program worked! I was running the loop from 0 which, I think, also
works. Sorry, I somehow posted an edited version of the program.

Change
ThisSum = 0;
to
ThisSum = A[0];
will avoid the bug. But I don't know this way whether will leading a
new bug in code.

If it were my coursework, I would submit
your version, because I think the maximal sub-sequence sum is zero
when all the elements are negative. You might be asked to explain why
you think it should not be!

Yes, you may be right, "Max" sub-sequence certain contain zero
element.So When all the elements are negative, "Max" equal to "zero",
But I think "Max" at least contain one elements.So.....

Thanks you try to express you meaning clearly to me,~~,my English is
so poor, luckily, at end I understand what do you want present.

I think I should enhance My English skills.

 

[xianwei]

In additional, I said about zero is zero elements, and not is zero
value.