GordonRamsay_'s blog

By GordonRamsay_, history, 2 years ago, In English

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?

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Compute prefix sum of array $$$a$$$, let it be array $$$pref$$$.

Create a map<long long,set<int>> ids by executing ids[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), and r2 = 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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!