Maximum subarray

Question

In the column 8 of "programming pearls". There is a maximum subarray problem.

Problem :

The input is a vector x of n floating-point numbers; the output is the maximum sum found in any contiguous subvector of the input. To complete the problem definition, we'll say that when all inputs are negative the maximum-sum subvector is the empty vector, which has sum zero.

The most efficient solution:

maxsofar = 0
maxendinghere = 0
for i = [0, n)
    maxendinghere = max(maxendinghere+x[i], 0)
    maxsofar = max(maxsofar, maxendinghere)

There is an exercise in this column: We defined the maximum subvector of an array of negative numbers to be zero, the sum of the empty subvector. Suppose that we had instead defined the maximum subvector to be the value of the largest element; how would you change the various programs?

I have two questions for this exercise (1) I'm kind of confused by "Suppose that we had instead defined the maximum subvector to be the value of the largest element". Does it mean the maximum subvector of an array of negative numbers to be the largest element in the array?

For example: Array : [-1 -2 -3], maximum subvector : -1 Array : [-1 2 3], maximum subvector : [2 3]

Sorry for this dummy question, English is not my naive language.

(2) The author gave the solution : "Replace the assignment maxsofar=0 with maxsofar = -infinity." It seems that this solution is not right based on my understanding of the question.

For example: Array : [-1 -2 -3], The answer should be -1. But according to the solution, it's 0.

Thanks,

Answer 1

I agree with you. If the author's solution is only to change the initialization of maxsofar then it doesn't change at all the algorithm.