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

Правка en3, от GordonRamsay_, 2022-05-31 17:16:30

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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский GordonRamsay_ 2022-05-31 17:16:30 18 Tiny change: 'ast enough\n\n' -> 'ast enough. Can you help me?\n\n'
en2 Английский GordonRamsay_ 2022-05-31 17:15:51 30
en1 Английский GordonRamsay_ 2022-05-31 17:14:47 824 Initial revision (published)