Программа Javascript для максимальной равновесной суммы в массиве

Дан массив arr[]. Найдите максимальное значение суммы префиксов, которая также является суммой суффиксов для индекса i в arr[].

Примеры :

Input : arr[] = {-1, 2, 3, 0, 3, 2, -1}
Output : 4
Prefix sum of arr[0..3] = 
            Suffix sum of arr[3..6]

Input : arr[] = {-2, 5, 3, 1, 2, 6, -4, 2}
Output : 7
Prefix sum of arr[0..3] = 
              Suffix sum of arr[3..7]

Простое решение состоит в том, чтобы один за другим проверить заданное условие (сумма префиксов равна сумме суффиксов) для каждого элемента и вернуть элемент, который удовлетворяет заданному условию с максимальным значением.

Временная сложность: O(n ² )
Вспомогательное пространство: O(n)

Лучшим подходом является обход массива и сохранение суммы префиксов для каждого индекса в массиве presum[], в котором presum[i] хранит сумму подмассива arr[0..i]. Сделайте еще один обход массива и сохраните сумму суффиксов в другом массиве suffsum[], в котором suffsum[i] хранит сумму подмассива arr[i..n-1]. После этого для каждого индекса проверьте, равно ли presum[i] suffsum[i], и если они равны, то сравните их значение с общим максимумом на данный момент.

Временная сложность: O(n)
Вспомогательное пространство: O(n)

Дальнейшая оптимизация:
Мы можем избежать использования дополнительного пространства, сначала вычислив общую сумму, а затем используя ее для нахождения текущих сумм префикса и суффикса.

Временная сложность: O(n)
Вспомогательное пространство: O(1)

Пожалуйста, обратитесь к полной статье о максимальной равновесной сумме в массиве для получения более подробной информации!