FastPrep
Problem · Array

Maximum Number of Moves with Same Result Sum

Learn this problem
● MediumGoogleFULLTIMEOA
See Google hiring insights

Problem statement

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: class Solution { public int solution(int[] A); }

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.

Function

solution(A: int[]) → int

Examples

Example 1

A = [3, 1, 5, 3, 3, 4, 2]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].

Example 2

A = [4, 1, 4, 3, 3, 2, 5, 2]return = 4
It is possible to delete the first and last elements four times, as each such pair of elements sums up to 6.

Example 3

A = [1, 9, 1, 1, 1, 1,1,1, 8, 1]return = 1
There is no way to perform move that results with the same sum more than once.

Example 4

A = [1, 9, 8, 9, 5, 1, 2]return = 3
The first move should delete the first two elements, then the second and third moves should delete first and last elements twice.

Example 5

A = [1, 1, 2, 3, 1, 2, 2, 1, 1, 2]return = 4
The function should return 4.

Constraints

  • 2 ≤ A.length ≤ 1000
  • -10^9 ≤ A[i] ≤ 10^9
  • After each move, the remaining elements preserve their original order.

More Google problems

drafts saved locally
public int solution(int[] A) {
  // write your code here
}
A[3, 1, 5, 3, 3, 4, 2]
expected3
checking account