What is circular subarray? And how kadane’s algo is working behind it? Means on what concept we are performing such calculations?
Circular Subaaray
lets consider an array 1 2 3 4 5 it would be called circular if we assume that 5 is connected to 1 i.e the last element is connected to the first.
Any Subarray which uses that circular property is called circular subarray, for example 4 5 1 we will call this wrapping subarray
Kadanes algorithm returns the maximum sum subarrray on the non circular subarray but if we multiply each number by -1 and then run kadanes algorithm and then multiply the result by -1 it’ll return minimum sum subarray in a non circular subarray.
Every time we select a subarray from a circular array it divides the circular array into two parts a wrapping subarray and a non wrapping subarray. we select the non wrapping subarray since the sum of the entire circular array is constant and sum of wrapping and non wrappping sub array is equal to sum of circular subarray, In order to maximize the wrapping subarray we need to minimize non wrapping subarray but kadanes algorithm only finds maximum sum subarray so thats why we invert sign cuz this way it’ll find minimum sum subarray rather than maximum and we’ll subtract it from circular sum to get maximum wrapping subarray sum.