Bug in findMaximumSubarray() in DP section?

#1

If I run the book code (which appears identical to the “solutions” code on this site) I see the following:

int m1 = findMaximumSubarray(Arrays.asList( 0, 0)); // returns 0
int m2 = findMaximumSubarray(Arrays.asList(-1,-1)); // returns 0 - what?
int m3 = findMaximumSubarray(Arrays.asList( 1, 1)); // returns 2
int m4 = findMaximumSubarray(Arrays.asList(-1, 1)); // returns 1

Why is a list of only two -1 values returning a max subarray sum of 0 instead of -1?

0 Likes
#2

Hi @jgrace,

It just means no elements are selected. So the subarray size is 0, which means the sum is 0 as well.

0 Likes
#3

Hi,

Thanks a lot Tsung-Hsien for your answer! I would also like to thank you a lot for writing this fantastic book!

I just bumped into the same issue as @jgrace. I could not find unfortunately any constraint saying that negative numbers can’t be a max sum. After googling a bit, it seems that this is called Kadane’s algorithm, which in this specific case would return -1, because the max sum is actually -1. I think that this could be pointed out better in the book to say that. Without the code ( minSum=0 ) I wouldn’t have figured it out…

Still, thank you again!

0 Likes