For the circular array 8, -1, 3, 4, compute the maximum sum of a contiguous non-empty subarray where the subarray may wrap around the end. Give the general algorithm and the input class on which the obvious version returns a wrong answer.

For the circular array 8, -1, 3, 4, compute the maximum sum of a contiguous non-empty subarray where the subarray may wrap around the end. Give the general algorithm and the input class on which the obvious version returns a wrong answer.

Approach: A wrapping subarray is the complement of a non-wrapping one, so the wrapping best is the total minus the minimum subarray. Then check what happens when the complement is empty.

15. The non-wrapping maximum from Kadane's algorithm is 8 - 1 + 3 + 4 = 14. A wrapping subarray is exactly the complement of a contiguous non-wrapping one, so the best wrapping sum is the total minus the minimum subarray sum, which is 14 minus -1, giving 15, achieved by 3, 4, 8 across the wrap. Taking the larger of the two gives 15. The general algorithm runs Kadane's twice in one linear scan, once for the maximum and once for the minimum, and reports max(bestNormal, total - bestMin), which is O(n) time and O(1) space. The failure case is an all negative array such as -3, -2, -5: the minimum subarray is the whole array, so total minus it is 0, which corresponds to the empty subarray and is not a legal answer. Guard it by returning the plain Kadane result whenever the maximum is negative, or by forbidding the minimum subarray from covering every element.

Follow-up: How do you find the maximum sum of a subarray of length at most k in a circular array in linear time?

Key concepts: kadane's algorithm, complement subarray, all negative case, linear scan.