# The Flipping Game Codeforces

I just learnt maximum subarray sum and tried implementing it in this problem, The Flipping Game, but I am getting WA on 1 test case.

Test case for which my code fails

100

0 1 0 1 1 1 0 1 0 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1

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.

See what your code is doing, let n=4.

``````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.

Hope it clearsâ€¦

2 Likes

Oh got it I am sorry

@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.

@damn_me thanks a lot, I understood my fault and got it accepted. However, for the following test case the corrected/accepted code returns 2 on my PC

3

1 0 1

But the actual answer is 3, because we can select 0 in our move and change it to 1, thus getting 3 1s and not 2. What could be the problem?

See the link again, 87RkJA - Online C++0x Compiler & Debugging Tool - Ideone.com 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.