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.
Write a function:
int solution (int A[J, int N) ;
that, 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.
Examples:
1. Given A = [3, 1, 5, 3, 3, 4, 2], the function should return 3. 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].
2. Given A = [4, 1, 4, 3, 3, 2, 5, 2], the function should return 4. It is possible to
delete the first and last elements four times, as each such pair of elements sums up to 6
3. Given A = (1,9, 1, 1, 1, 1, 1, 1, 8, 1], the function should return 1. There is no way
to perform move that results with the same sum more than once.
4. Given A = [1, 9, 8, 9, 5, 1, 2], the function should return 3. The first move should
delete the first two elements, then the second and third moves should delete first and last elements twice.
5. Given A = [1, 1, 2, 3, 1, 2, 2, 1, 1, 2], the function should return 4. One of the
Dossible secuence of moves aoes as follows:Examples:
1. Given A = [3, 1, 5, 3, 3, 4, 2], the function should return 3. 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].
2. Given A = (4, 1, 4, 3, 3, 2, 5, 2], the function should return 4. It is possible to
delete the first and last elements four times, as each such pair of elements sums up to 6.
3. Given A = [1, 9, 1, 1, 1, 1, 1, 1, 8, 1], the function should return 1. There is no way
to perform move that results with the same sum more than once.
4. Given A = [1, 9, 8, 9, 5, 1, 2], the function should return 3. The first move should
delete the first two elements, then the second and third moves should delete first and last elements twice.
5. Given A = [1, 1, 2, 3, 1, 2, 2, 1, 1, 2], the function should return 4. 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.
Write an efficient algorithm for the following assumptions:
• 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].