Разделить массив на максимальное количество подмассивов, чтобы сумма чередующихся сумм была равна 0

Дан массив arr[] из 1 и -1, задача состоит в том, чтобы разбить массив на максимальное количество подмассивов так, чтобы сумма переменной суммы всех подмассивов была равна 0. Выведите диапазоны подмассивов и количество подмассивов.

Примечание. Переменная сумма подмассива a[] определяется как a[0] – a[1] + a[2] – a[3] . . .

Examples:
Input: {-1, 1, 1, 1, 1, 1}
Output: 
{0, 0}, {1, 1}, {2, 3}, {4, 5}
4
Explanation: From index 0 to 0 the alternating sum is -1. From 1 to 1 the alternating sum is 1. From index 2 to 3 and index 4 to 5 the sum is 1 – 1 = 0. The sum of the alternating sums is -1 + 1 + 0 + 0 = 0. So these are two partitions whose sum of alternating sums is 0.

Input: {1, 1, 1, 1}
Output:
{0, 1}, {2, 3}
2

Подход: Эту проблему можно решить, используя следующую идею.

Since the only elements present in the array are 1 and -1 for any two consecutive elements there are 4 possibilities in total  like {1, 1}, {1, -1}, {-1, 1}, {-1, -1} the alternating sum in the 4 cases is :

{1, 1} -> 1 – 1 = 0;
{1, -1}-> 1 + 1 = 2;  —> In this case it can be considered as {1}, {-1} => 0
{-1, 1}-> -1 – 1 = -2; —> In this case it can be considered as {-1}, {1} => 0
{-1, -1}-> -1 + 1 = 0;

In the first and fourth case the alternating sum is 0 so in that case they can be considered as one subarray and in remaining two cases individual element is considered as a subarray.

Выполните шаги, указанные ниже, чтобы решить проблему:

• Проверьте, является ли размер массива нечетным, если размер нечетный, сумма чередующихся сумм не может быть равна 0, поэтому выведите -1.
• Теперь пройдите через массив и проверьте каждые два соседних, если они имеют одинаковый знак, а затем рассмотрите оба как подмассив, иначе рассмотрите оба как разные подмассивы.
  • Если знаки совпадают, подмассив находится в диапазоне {i, i+1} и увеличивает счетчик на 1.
  • В противном случае подмассивы равны {i, i} и {i, i+1} и увеличивают счетчик на 2.
• Наконец, распечатайте подмассивы и подсчитайте подмассивы.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N), где N — размер массива
Космическая сложность: O(1)