I tried debugging and figured out that something is wrong with the maximum sub array function of my program. But couldn’t fix it. Kindly help me understand my error.
call func(a,4)
m=4/2 = 2
/ \
func(a,2) func(a,(4-2)) -> see below why this is incorrect.
m= 2/2=1
/ \
func(a,1) func(a,1)
| |-> this call also returns a[0] which is incorrect, call is for the range (2,2)
\|/
this left call returns a[0] which is correct
In the call func(a,(4-2)) i.e. right recursive call, you intend calculating sum of the range[3,4]. But how does your code know that? You have just passed (a,2) which has nowhere mention of the fact that it corresponds to the range [3,4]. It assumes it to be [0,2] which is absolutely wrong. The call proceeds in the manner your left call func(a,2) proceeds. That’s why upper and lower limit of every range is required in every step of recursion which is different for every recursive call.
I changed your code to this and it works fine, However, there’s a simple O(n) approach(Kadane’s algorithm) for finding the maximum subarray which you can see here.
@damn_me I am so sorry, I really didn’t get what you are trying to say. The 2nd recursive call will return maximum of (0 to 25) and (26 to 50) i.e. ((51/2)+1 to 50) not (25 to 50). I still don’t understand why right halves and left halves are not (mid+1,n) and (0,mid) in all recursive calls.
I read about Kadane’s algorithm as well but wanted to employ Divide and Conquer in this problem to enhance my understanding of recursion.
I edited above with the visual of how recursion is proceeding. I think it’ll help, any doubt ask freely Also, I’d suggest see some video of the same… that may make it more clear.
See the link again, http://ideone.com/87RkJA Line 11, it should return a[low], the code gives 3 now. This is the correct answer and the previous accepted one gave wrong as 2. You can please write to the codeforces team as their online judge accepted a wrong solution orlet me know if you haven’t done yet, i’ll mail them.
