Google OA 2024 - Maximum Number of Partitions

You are given an array of integers. Your task is to determine the maximum number of partitions you can make. A partition divides the array into two parts such that the sum of the elements in each part is equal. Additionally, you are allowed to perform one operation where you can change any single number in the array to 0. 

Test Case :

Input: [-1, 5, 0, 0, 5, 0]  

Output: 3 

Explanation: By changing -1 to 0, you can make three partitions where the sums of the two parts are equal.

Expected Time Complexity: O(n)