https://online.codingblocks.com/app/player/79595/content/76009/5302/code-challenge
I am unable to solve this problem. I know Kadane’s algorithm but I’m not quite getting how to extend it to a circular array. If this problem can’t be solved by Kadane’s algorithm please explain me how to solve this problem.
@Ibrahim Yes you are thinking correct, you can apply Kadane Algo.
Just modify it, here you need to apply it on a circular array.
So take every index of the array as starting pointing of the array with previous index as ending point.
Just applying kadane for every index as start point.
Feel free to ask if you face any difficulty in implementing this. You can also ping me on chat.
Sir I am not getting what you are trying to say, could you please explain this by an example?
For eg:- 8 -8 9 -9 10 -11 12
just take every index as start point.
Here, lets first take, start=0 , end = 6. Then just apply kadane , where loop will be like for(int i=st; i<=end; i++)
similarly, then take, start = 1, end=0. Here elements of the array will be like from(1, 6) then (0)
similarly, start=2, end=1. Here elements of the array will be like from(2, 6) then (0, 1)
So you will need to traverse the array in the circular manner.
for that you can use a do-while where start and end are intialized as same value.
at every step start is updated as start = (start+1)%n.
I have implemented the code for this, you can refer to this if you are facing difficulty to implement this https://ide.codingblocks.com/s/218572
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.