Максимизируйте сумму абсолютной разницы между соседними элементами в массиве с суммой K

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

Даны два целых числа N и K , задача состоит в том, чтобы максимизировать сумму абсолютных разностей между соседними элементами массива длины N и суммы K .

Примеры:

Input: N = 5, K = 10 
Output: 20 
Explanation: 
The array arr[] with sum 10 can be {0, 5, 0, 5, 0}, maximizing the sum of absolute difference of adjacent elements ( 5 + 5 + 5 + 5 = 20)

Input: N = 2, K = 10 
Output: 10 

Подход:
Чтобы максимизировать сумму соседних элементов, выполните следующие действия:

  • Если N равно 2, максимальная возможная сумма равна K , если поместить K в 1 индекс и 0 в другой.
  • Если N равно 1, максимально возможная сумма всегда будет равна 0.
  • Для всех других значений N ответ будет 2 * K.

Illustration: 
For N = 3, the arrangement {0, K, 0} maximizes the sum of absolute difference between adjacent elements to 2 * K
For N = 4, the arrangement {0, K/2, 0, K/2} or {0, K, 0, 0} maximizes the required sum of absolute difference between adjacent elements to 2 * K

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

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

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