You are given two nonempty arrays of positive integers, a and b. In either array, you may replace a contiguous group of elements with one element equal to their sum. You may repeat this operation independently on both arrays.
Implement maxCommonLength(a, b). Return the maximum possible length of the resulting arrays when they are exactly equal, element by element. Return -1 if they cannot be made equal.
Rules and Constraints
-
Merging preserves element order. You may merge adjacent groups but cannot split an element, reorder elements, or remove values.
-
You may perform no operations on an array that already has the desired form.
-
Each array has between 1 and 100,000 elements. Every value is between 1 and 1,000,000,000.
-
Intermediate and total sums must be represented exactly.
Example 1
a = [1, 2, 3, 3]
b = [3, 3, 3]
Output: 3
Merge the first two elements of a to obtain [3, 3, 3]. Length 3 is maximal because b starts with only three elements and merging cannot increase its length.
Example 2
a = [1, 2]
b = [4]
Output: -1
No allowed sequence of merges makes these arrays equal.