Максимальная сумма префиксов, равная сумме суффиксов, так что префикс и суффикс не перекрываются

Опубликовано: 25 Февраля, 2023

Учитывая массив arr[] из N положительных целых чисел, задача состоит в том, чтобы найти наибольшую сумму префиксов, которая также является суммой суффиксов, а префикс и суффикс не перекрываются.

Примеры:

Input: N = 5, arr = [1, 3, 2, 1, 4]
Output: 4
Explanation: consider prefix [1, 3] and suffix [4] which gives maximum 
prefix sum which is also suffix sum such that prefix and suffix do not overlap.

Input: N = 5, arr = [1, 3, 1, 1, 4]
Output: 5

Подход: Задача может быть решена с помощью метода двух указателей.

Use two pointers from both ends of array and keep maintaining sum of prefix and suffix, keep moving pointers till they overlap. 

Следуйте инструкциям, чтобы решить проблему:

  • Объявите и инициализируйте две переменные i = 0 и j = N – 1 .
  • Объявите и инициализируйте две переменные для хранения суммы префикса и суффикса, prefix = 0 , suffix = 0 .
  • Объявите и инициализируйте переменную result, чтобы сохранить максимально возможную сумму префикса, result = 0 .
  • в то время как я меньше или равен
    • Если сумма префикса меньше суммы суффикса , добавьте элемент массива по i- му индексу к сумме префикса и увеличьте значение i .
    • В противном случае добавьте элемент массива по j -му индексу к сумме суффиксов и уменьшите значение j.
    • Если они оба равны, обновите переменную результата с префиксом sum .
  • Вывести значение результата .

Ниже приведена реализация описанного выше подхода.

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ