Please check the sollution of this question
Hello @kartiksaxena2000,
-
Can you explain your approach to keep track of
1.1. if the maximum sum is present in a linear fashion
1.2. if the maximum sum is present in circular fashion. -
You can reduce the time complexity of this program:
This question can be solved in O(tn)
But, your program is taking O(tn*n)
You have to use kadane’s algorithm to solve this:
-
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). -
Compare max1 and max2.
-
Print the maximum of both.
Hope, this would help.
Give a like if you are satisfied.
ok i understand that
but can u please check what am i wrong in
Sure @kartiksaxena2000,
There are two issues with your problem:
-
The third if condition:
When j becomes n-1, you are assigning it 0. Which seems correct as you wants to add elements from j=0 to j=i-1.
But, it is skipping the index j=0.
Reason:
after executing that if condition, control goes to the start of the loop and the value of j increments to 1. Thus, it would never check for j=0.
Solution:
j=-1; -
Your code would not work for i=n-1.
Reason:
the loop of j starts from i+1 and iterates till j <n
for the case, when i=n-1, j=i+1=n-1+1=n
So, it will terminate
I modified your code:
Hope, this would help.
Give a like, if you are satisfied.
was my approach alright
and if not what would be a more smart way
Hello @kartiksaxena2000,
Your approach takes O(n^2) time complexity i.e. there are two nested loops.
You can further reduce the complexity to O(n) i.e. without any nested loops.
For, this approach read my very first reply on this thread.
I have explained the efficient way there.
Hope, this would help.
If you still have any issue, feel free to ask.