This is a question from the book Algorithms by Jeff Erickson.
Suppose A is a circular array. In this setting, a “contiguous subarray” can be either an interval A[i .. j] or a suffix followed by a prefix A[i .. n] · A[1 .. j]. Describe and analyze an algorithm that finds a contiguous subarray of A with the largest sum. The input array consists of real numbers.
There are two possibilities
1.) No Wrapping around (We can use Kadane's Algorithm)
2.) Wrapping around(ie; Starting index of the subarray is greater than the ending index) (I have doubt in this case)
Now return the maximum of two cases as result.
For the second case, searching on the internet provided an approach without proof.
The approach is to find the subarray with minimum sum and subtract it from the sum of the entire array (ie; sum(A) - min_subarray_sum(A)). How is this solution correct?
Link for the method used in the second case: https://www.geeksforgeeks.org/maximum-contiguous-circular-sum/