Максимизируйте сумму абсолютной разницы между соседними элементами в массиве с суммой K
Даны два целых числа 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)