Question about Maximum Subarray Sum problem (chapter 17)

#1

In the Maximum Subarray Sum problem in the beginning of chapter 17, it is said that “for each index j, the maximum subarray ending at j is equal to S[j] - min S[i] with i<=j”. However, I assume that the maximum subarray will be [i + 1, j]. Thereby, if i = j, the maximum subarray will be [j + 1, j] which seems invalid.
Should it be “S[j] - min S[i] with i < j” (i is strictly less than j)?

I tested the following implementation with the “i < j” condition.

pair<int, int> FindMaximumSubarray(const vector<int>& A) {
        // A[max_range.first : max_range.second - 1] is the maximum sequence in A
        // This is just for compatible with the code in the EPI book
        pair<size_t, size_t> max_range(0,0);

        if (A.size() <= 1) return {0,1};

        int subsum = 0, max_sum = std::numeric_limits<int>::min(),
            min_sum = 0, min_sum_idx = -1; // A[-1] is 0
        for (size_t i = 0; i < A.size(); ++i) {
                subsum += A[i];

                if (subsum - min_sum > max_sum) {
                        max_sum =  subsum - min_sum;
                        max_range = {min_sum_idx + 1, i + 1};
                }

                if (subsum < min_sum) {
                        min_sum = subsum;
                        min_sum_idx = i;
                }
        }
        return max_range;
}
0 Likes
#2

I think it depends on how you define the subarray. Here we thinks a subarray could be built with 0 elements.

BTW, you might to use the testing framework in https://github.com/epibook/epibook.github.io/blob/master/solutions/cpp/Max-sum_subarray.cc for testing your algorithm. Let me know if you find any problem.

0 Likes