Given an array length n, 0 <= a[i] <= 10^9, n <= 20000 Split the array into two parts such that they have equal sum, when we split, we can choose left or right to continue the process , each split give us 1 point. Return the maximum point you can get.
Test Input: n:3, a = 3 3 3 Output: 0 (we can't split the array so that they have equal sum)
n:4, a = 2 2 2 2 Output: 2 (we can split the array into 2 2, 2 2 => then we can choose to continue with either left or right to 2, 2)
n:7, a = 4 1 0 1 1 0 1 Output: 3 (split into 4, 1 0 ...) then continue with 1 0 1 1 0 1 and so on.
My idea is to run a loop from l to r-1 check if sum(l,i) = sum(i+1,r) then i'll recursion to get the max But obviously, my solution isn't fast enough. Can you help me?
Compute prefix sum of array $$$a$$$, let it be array $$$pref$$$.
Create a
map<long long,set<int>> idsby executingids[pref[i]].insert(i)for all valid $$$i$$$.Let $$$solve(l,r)$$$ is a recursive function such that the answer is $$$solve(1,n)$$$.
If $$$pref[r]-pref[l-1]$$$ is odd then return $$$0$$$, else if $$$pref[r]-pref[l-1] = 0$$$ then return $$$r-l-1$$$.
Set
mid = (pref[r]+pref[l-1])/2,l2 = ids[mid].lower_bound(r), andr2 = ids[mid].lower_bound(l).Again if $$$l2 = r2$$$ then return $$$0$$$, else return
1 + max(solve(l,*r2),solve(1+*--l2,r)).Notice that function $$$solve$$$ will only called $$$O(n)$$$ times and each function call only needs $$$O(log n)$$$ time.
Really appreciate your comment. But can you explain it more clearly? I understood "If pref[r]−pref[l−1] is odd then return 0, else if pref[r]−pref[l−1]=0 then return r−l−1." but I didn't understand your solution, thank you!