Maximum Number of Moves with Same Result
You are given an array A consisting of N numbers. In one move you can delete either the first two, the last two, or the first and last elements of A. No move can be performed if the length of A is smaller than 2. The result of each move is the sum of the deleted elements.
Given an array A of N integers, returns the maximum number of moves that can be performed on A, such that all performed moves have the same result.
Warmest thanks to the ever-amazing spike!(๑ᵔ⤙ᵔ๑)
1Example 1
The first move should delete two last elements (4 and 2 with sum = 6), then A = [3, 1, 5, 3, 3]. The second move may delete first and last elements (3 and 3 with sum = 6), then A = [1, 5, 3]. The third move should delete first two elements (1 and 5 with sum = 6), then A = [3].
2Example 2
It is possible to delete the first and last elements four times, as each such pair of elements sums up to 6.
3Example 3
There is no way to perform move that results with the same sum more than once.
4Example 4
The first move should delete the first two elements, then the second and third moves should delete first and last elements twice.
5Example 5
One of the possible sequence of moves goes as follows: twice delete the last two elements, then delete the first and last elements, last move deletes the first two elements.
Constraints
Limits and guarantees your solution can rely on.
- N is an integer within the range [1..1,000];
- each element of array A is an integer within the range [1..1,000,000,000].