Circular array sum

#1

Is there any other method to solve this problem other then in which we just simply make the array elements negative and calculate maximum sum and do the rest calculation…

#2

To solve this question apply Kadane algorithm (used to find min/max sum in subarray). Find the maximum sum(m1).
Now as array is circular find the minimum sum from Kadane, then second canditate for max sum(m2)= Total sum-min_sum.
Take maximum of both (m1,m2) to get final answer.

#3

Yes I know this one but other then this… Is there any approach because on first thought I could not be able to think like this…

#4

Optimum approach is this only(I will try to see if anything else is possible in O(n)). Using other method like prefix sum etc will result in O(n^2).
Its not necessary that you get the correct approach for every problem on seeing it first time only. Solving questions is best way to increase our familiarity and to know more techniques.

#5

How can we do it by prefix sum??

#6

First apply Kadane algorithm to get maximum sum of sub array in the array.
Create a prefix sum array and suffix sum array. Now for for any pre[i] try to add it with any suff[j] (j>i)
Now compare sums obtained from both method to get final answer.

1 Like
#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.