CMPS 144L Lab Activity: Maximum Segment Sum, Recursively

Background

If a[] is an array with length N (i.e., N = a.length), then, for any pair of integers (k,m) satisfying 0≤k≤m≤N, a[k..m) refers to the portion of a[] beginning at location k and extending up to, but not including, location m. We refer to this as an array segment. A special case of an array segment is the whole array: take k to be 0 and m to be N. Another special case is an empty segment: take k and m to be equal. (Indeed, one can interpret it to be that each of a[0..0), a[1..1), ..., a[N..N) is a distinct empty segment of a!)

Of course, an array segment has subsegments. Specifically, if a[k..m) is an array segment, then, for any pair (k',m') satisfying k≤k'≤m'≤m, a[k'..m') is a subsegment of a[k..m). A special case of a subsegment is a prefix: a[k'..m') is a prefix of a[k..m) if k = k' ≤ m' ≤ m. An analogous special case is a suffix: a[k'..m') is a suffix of a[k..m) if k ≤ k' ≤ m' = m.

Now, if a[k..m) is a segment of an array that contains values of a numeric type (e.g., int, double, or even Integer), it makes sense to refer to its sum, meaning the sum of the elements that it contains: a[k] + a[k+1] + ... + a[m−1].

The Maximum Segment Sum problem is this: Given an array segment (or, as a special case, an entire array), determine the maximum among the sums of all its subsegments.

For example, consider the array a[] pictured below. Among all its segments, the largest of their sums is 16. Indeed, there are four segments having that sum: a[2..8), a[5..8), a[11..16), and a[18..22).

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
3	−8	5	1	−6	12	−5	9	−2	−10	−8	1	2	5	−2	10	−7	−11	2	10	−5	9	−13	5	2	−3

Your Task

Provided is the java class MaxSegSum_S25. It includes a method maxSegSumA() that, as its name suggests, computes the maximum segment sum of a given array segment. (There are actually two methods with that name, the second of which is the one just referred to, which accepts three parameters.)

By examining the body of the method, you can observe that it does its work in a recursive manner, based upon these facts regarding any array segment a[low..high) (with 0≤low≤high≤a.length):

• If low == high, a[low..high) is an empty segment having only itself as a subsegment. The sum of the elements in an empty segment is obviously zero.
• If low < high, the subsegments of a[low..high) can be partitioned into the prefixes of a[low..high) and the subsegments of a[low+1..high). Hence, to the maximum segment sum of a[low..high) is the larger among the maximum sum among all prefixes of a[low..high) and the maximum sum among all subsegments of a[low+1..high).

T(n)	category	How to Tell
O(logc n)	logarithmic	T(cn) ≈ T(n)+1
O(n)	linear	T(cn)/T(n) ≈ c
O(n·logc n)	log-linear	T(cn)/T(n) ≈ c + c/logc n
O(n2)	quadratic	T(2n)/T(n) ≈ 4
O(n3)	cubic	T(2n)/T(n) ≈ 8
O(cn)	exponential	T(n+1) ≈ c·T(n)

Run the program. It prompts the user to enter

1. the length of the array to be processed,
2. a seed for the instance of java.util.Random that will be used for generating the array elements
3. the minimum allowed array element value, and
4. the maximum allowed array element value.

Make sure to choose a negative number for the minimum allowed array element value, because otherwise the maximum segment sum of the array will necessarily be the sum of all its elements, which is not an interesting case. Indeed, choose the minimum and maximum allowed values to be similar in their magnitudes.

Run the program several times using arrays of lengths 10, 20, 40, etc., (doubling the length each time) and observe the values reported by the program for how many method calls occurred and the maximum depth to which the recursion descended.

Use those values and the table to the right to try to determine the complexity class of the running time of maxSegSumA(), and likewise for its maximum recursion depth. Discuss it with your lab instructor.