Circular sum Concept issue

#1

sir mujhe yeh samjh me aagya ki , coding me kya kya krna h jaise,
pehle kadane sum nikalo simply , then ek wrap sum and ek inverted array ka kadane sum , then wrap and inverted sum ko add kro , agr vo normal kadane se bada h than that is the ans otherwise, kadane vaala is the ans .

but mujhe background logic samajh nhi aaya ki humne wrap sum kyu niakla , inverted vaala nikal ke usse kyu add kiya , kyu compare kiya then , toh aap please mujhe detail me expalin krdenge , aisa kyu kiya hai please…

#2 
We have to consider two cases while solving this problem:
Case 1: When the maximum sum SubArray is present in the normal order of array.
Example,
{-10, 2, -1, 5}
Max sum is 5

{-2, 4, -1, 4, -1}
Max sum is 7 (4+(-1)+4)
Use Kadane’s algorithm

Case 2:When max sum subArray is Present in circular fashion.
Inversion of the array is required only to find the maximum sum in circular fashion.
Example,
{10, -12, 11}
The max sum is 21 (11+10)
Inverted array, {-10,12,-11} //change of sign
Maximum sum is 12
Cumulative sum of original array is 9
Max sum=9+12=21

{12, -5, 4, -8, 11}.
The max sum is 23 (11+12)
Inverted array, {-12,5,-4,8,-11}
Maximum sum is 9 (5+(-4)+8)
Cumulative sum of original array is 14
Max sum=14+9=23

Note:
Inversion is done to apply Kadane’s algorithm which finds the maximum sum.

Hence, the maximum sum of inverted array would be the minimum sum of the original array.

Then, we will add the maximum Sum of inverted array with the Sum of all the elements of the original array(i.e. cumulative sum).
Suppose, cumulative sum is S=s-a
and max sum of inverted array is a
Adding both S+a=s-a+a=s(required sum)

Steps:
1.Find sum using both cases

2.At last compare the max sum obtain from both the cases
3. print the larger one.
1 Like