DP "maximum subarray sum" meaning on page 309 in EPI Java

#1

Hi all, I can’t seem to find if this has been asked before (apologies if duplicate question):

On page 309 of EPI Java wrt to DP:

I’m unclear as to what “maximum subarray sum” means:

[…] we also return the maximum subarray sum l for a subarray ending at the last entry in L, and the maximum subarray sum r for a subarray starting at the first entry of R.

Screenshot

UPDATE 1:

I figured out that “maximum” in “maximum subarray sum” means “for all the subarrays possible, which subarray would have the largest sum.” Previously I was thought maximum was referring to the length of the subarray.

Less important now, but another point of ambiguity for me is the 2nd portion of the verbiage: “subarray ending at the last entry in L, and the maximum subarray sum r for a subarray starting at the first entry of R” (not sure the significance of the “last entry” vs. “first entry”)

kw: Dynamic Programming

0 Likes
#2

Hi @killabyte,

It is a very high-level description of divide and conquer approach, and we would like to rewrite this part in the next edition as it probably it not the best way to present the idea we want to show here.

0 Likes
#3

I’ve been banging my head against the wall for a few minutes when I read the sentence quoted in the original post, although I’m reading it on page 277, Chapter 17 EPI C++ 1.5.0 and in my case it reads
we also return the maximum subarray sum l for a subarray ending at the last entry in L, and the maximum subarray sum r for a subarray starting at 0 for R.

I think “maximum subarray sum” indeed means “the maximum of the sums of elements of all subarrays”.

The “last entry in L” part means that while finding the “maximum subarray sum” of all subarrays of L we will also find the maximum sum of elements of all subarrays that end at the last elements of L. Recall that L includes elements with indices [0…n/2], so to compute l we will find the max of sums of elements of all subarrays containing elements with indices [k…n/2] where k is [0…n/2].

Similarly for r we will find the max of sums of elements of all subarrays containing elements with indices [n/2…k] where k is [n/2…n].

Then the max of the sums of elements of all subarrays that partially lay in L and partially in R will indeed be l+r. Then the “maximum subarray sum” of all subarrays of A is indeed max of “maximum subarray sum” of L, “maximum subarray sum” of R and l+r.

0 Likes