Maximum number of times we can split the array into two part such that they have equal sum

Revision en1, by GordonRamsay_, 2022-05-31 17:14:47

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: 3 3 3 3 Output: 0 (we can't split the array so that they have equal sum)

4 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)

7 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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English GordonRamsay_ 2022-05-31 17:16:30 18 Tiny change: 'ast enough\n\n' -> 'ast enough. Can you help me?\n\n'
en2 English GordonRamsay_ 2022-05-31 17:15:51 30
en1 English GordonRamsay_ 2022-05-31 17:14:47 824 Initial revision (published)