Please provide hint

#1

unable to solve’ please provide hint

Maximum circular sum..i am not able to build logic...coudl you explain me whats the logic behind it
#2

Hello @kartik-malik,

Here, you have to considered the given array as a circular sequence.
example:
for the array : {-1,2,8,-5,6}
the sub-sequences are:
{-1}=-1
{-1,2} = 1(sum)
{-1,2,8} = 9
{-1,2,8,-5}= 4
{-1,2,8,-5,6} = 10
{2]=2
{2,8} = 10
{2,8,-5}=5
…
…
{6}=6
{6,-1}=5 (coz array is considered circular)
{6,-1,2} =7
…
print the maximum.

First, create a program with nested loop, with complexity O(N)
this would help you understand the approach.
then, try to reduce the complexity to O(N)

You have to use kadane’s algorithm to solve this:

  1. Find the maximum sum possible in circular manner:
    …First negate all the elements of the array. i.e. covert negative nos. to positive and vice-a-versa example: 1- to 1 and 5 to -5.
    …Now, apply kadane’s algorithm on this modified array and find maximum value which the minimum value for actual array(say min2).
    …At last, add this min2 to the sum of all the elements of the actual array (say max2).
  2. Compare max1 and max2.
  3. Print the maximum of both.

If you still face problem, feel free to ask.
Hope, this would help.

Can you explain run error please
#3

please explain how the modified array is helpinh

#4

Hey @kartik-malik,

If we’ll negate all the values then we will get the contribution of the remaining elements.
Remaining elements: elements of array which were not involved in the maximum sum i.e. max1 computed by using kadane’s on the original array without negation.

#5

please review my code all test cases are wrong https://ide.codingblocks.com/s/271323

#6

Hey @kartik-malik,

Cross verify your code with the following:

Let me know if you can’t find the mistake, I’ll correct it for you.