all test cases are wrong please help
Maximum Circular Sum
Piyush, the approach you are trying to use is wrong,
You need to follow up the following approach as,
In this problem, there can be two cases i.e. either the subarray having maximum sum is obtained in a circular fashion or the subarray having maximum sum is obtained in a non- circular fashion.
The non-circular maximum sum subarray can be obtained directly by Kadane’s Algorithm.
But the subarray with circular fashion cannot be solved by Kadane’s algorithm.
So to solve this problem we will first calculate the maximum sum subarray using Kadane’s
Algorithm and store it in a variable, say candidate1. Then we will invert the sign of every
element of the array and again apply Kadane’s Algorithm to calculate the maximum sum
subarray of this new inverted array.
But we should keep in mind the fact that the maximum sum of the inverted subarray is actually
the minimum sum subarray for the original array. So if we subtract the negative value of this
new sum from the cumulative sum of the original array we will get another candidate for the
answer and name it candidate2. Then compare both the candidates and return the larger
number.
Try to implement this logic in your code and then try to submit the code…
can you explain how my approach is wrong
You have only consider the case when subarray having maximum sum is obtained using directly by kadane’s algorithm, and neither you have inverted the array and solved it using the circular fashion …Thts why all test cases were wrong… Try to implement the logic which I have discussed with you… Its also given in the pdf in the array section only…
i have checked the pdf and one thing that i dont understand is the last line inn which it is said that we have to remove all the negative values of the sub array from the cumulative sum, what is that and why are we doing this