Before reading the editorial, please make sure you've read the problem thoroughly multiple times and tried your best to solve it. Thanks!
Proceed to Editorial
Let us number the rice balls from 1 to N.
Let `DP[i][j]` be 1 if we can combine the rice balls from i to j into a single rice ball, and 0 otherwise.
Obviously, `DP[i][i] = 1` for all 1 ≤ i ≤ N.
Then `DP[i][j]` is 1 if there exists an index *k* that we can choose such that `sum(A[i..k]) = sum(A[k + 1..j])` and `DP[i][k] = 1` and `DP[k + 1][j] = 1`.
This means that we can combine if we can combine two sub rice balls with the same size, where both sub rice balls can be formed.
Second, we can combine the range i..j if there exists two indices *a* and *b* such that `sum(A[i..a]) = sum(A[b..j])` and `DP[i][a] = 1` and `DP[b][j] = 1` and `DP[a + 1][b - 1] = 1`.
To speed up the sums, we can use a prefix sum array.
Naively implemented, this is O(N4). To improve this, note that we can use a two-pointer method to compute all valid pairs (a, b).
Note that if `sum(A[i..a]) > sum(A[b..j])`, we should decrement b. Furthermore, if `sum(A[i..a]) < sum(A[b..j])`, we should increment a. This reduces the complexity of finding all pairs (a, b) to O(N).
Time Complexity: O(N3).